One Pager Cheat Sheet

• We'll use an efficient method which has an O(n) time complexity and O(1) space complexity to find the longest substring without repeating characters in a string of length 100000 or less which only contains lowercase letters.
• The problem of finding the longest substring with no repeated characters can be solved by manually checking every substring with a brute force approach.
• Our optimized solution efficiently solves the problem with respect to time, while requiring very little extra space, by dynamically tracking the last seen character element and jumping straight to the next valid substring when a duplicate is spotted.
• This algorithm finds the longest substring without duplicates by iterating through each character in the string and using lastPos to store the last occurrence of the character.
• The time complexity of the algorithm discussed is O(n) and the space complexity is O(1) or, depending on the size of the alphabet, O(A).

This is our final solution.

To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.

xxxxxxxxxx

}

var assert = require('assert');

​

var lengthOfLongestSubstring = function (s) {

  var startNum = 0,

    maximumLen = 0;

  var map = new Map();

​

  for (var i = 0; i < s.length; i++) {

    var ch = s[i];

​

    if (map.get(ch) >= startNum) startNum = map.get(ch) + 1;

    map.set(ch, i);

​

    if (i - startNum + 1 > maximumLen) maximumLen = i - startNum + 1;

  }

​

  return maximumLen;

};

​

try {

  assert.equal(lengthOfLongestSubstring('algodaily'), 7);

​

  console.log(

    'PASSED: ' +

      "`lengthOfLongestSubstring('algodaily')` should be equal to `7`"

  );

} catch (err) {

  console.log(err);

}

​

try {

  assert.equal(lengthOfLongestSubstring('thisisatest'), 5);

Great job getting through this. Let's move on.

If you had any problems with this tutorial, check out the main forum thread here.