However, at O(n^2), this is way too inefficient. Let's determine a better solution. At a quick glance, we know we'll need to iterate and have some form of on-going storage for tracking purposes.

Solution to Longest Substring Without Duplicate Characters

Our optimized method solves the problem efficiently with respect to time, yet requires very little extra space. Remember the manual steps our brute force approach above? Oftentimes, efficient solutions just cut out steps from slower ones.

Consider the step by step we already did. I highlighted/bolded some steps we probably don't need:

1. First, we consider a. Longest max is 1.
2. Then, we look at al. Longest max is now 2.
3. We look at alg. It's now 3.
4. o - 4
5. d - 5
6. a - wait, we've seen this before. Max is still 5, and the next few steps are also invalid and won't change the max. 1. We have substring algodai - i - substring has duplicate, so invalid 1. algodail - l - substring has duplicate, so invalid 1. algodaily - y - substring has duplicate, so invalid
7. Now we can start from l, and repeat from step 1... (l, lg, etc.)

Notice something? The last 3 steps before we start from l could've been cut out! We knew that once we encountered the second a, all substrings that we extended to would be invalid. So why don't we jump straight to starting from l as soon as we see the duplicate?

That's the idea behind the optimal solution.

More Setup

To find the longest substring with no repeating characters, we'll read each character of the input string from left to right.

At the same time, we'll keep track of the current substring and the maximum substring length found so far. To keep track of the current substring, we'll record its starting index in a variable startInd and its last index in a variable i.

This solution uses an array, which has the same size as the size of the alphabet. The array stores the index of the character of the alphabet last found in the input string (in other words, it's tracking the last seen character element). In this tutorial, we call this array lastPos.

1const lastPos = [];

As we read the characters, we'll also maintain the lastPos array for storing the index of each character's last occurrence in the string. The lastPos array would be initialized to -1.

Suppose at index position i, we have read character x. Before that, we would've encountered this character at lastPos[x]. lastPos helps us remember where we last saw a duplicate character. That way, we can use lastPos[x] + 1 to "remove" the first duplicate from the current substring, and test against a valid substring.

Cases

There are two possible cases that are occurring, which are shown in the figure and explained below. For now, we'll assume that lastPos can be indexed by x. Later we'll discuss how to implement the indexing for this array.

These two cases help us make sense of when to start or stop consideration of the current substring.

1. Case 1: x has already occurred in the current substring. In this situation startInd <= lastPos[x].

   To handle this case, start a new substring after lastPos[x]-- to do this, we can do startInd = lastPos[x]+1. Update the length of the current substring as (i-startInd+1).

2. Case 2: x has either not occurred in the string or it has occurred in some previous substring. In this case, startInd > lastPos[x] and we can read the next character of the input string and keep updating length and maximum length found so far.

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);

You're doing a wonderful job. Keep going!

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