The Longest Substring With No Repeating Characters

Today's algorithm of the day is one of the most popular ones on Leetcode:

Given a string, find the length of the longest substring without repeating characters.

For example, given the string "abbacda", the output of the function should be 4. The longest substring with no repeating characters is "bacd".

Some approaches to this problem use multiple nested loops, and end up with a huge Time Complexity (sometimes O(n^3)). In this post, I'll be walking through a solution of O(n) time and O(n) space. Because I think this is the kind of problem where the code makes more sense after an explanation, I'll start by using an example with pseudocode, and then code the solution using JavaScript.

In this problem, I'll make a set, and traverse through the given string with two pointers. If the right pointer gets to a character that's already in the string, then the left pointer will be moved over. We'll keep track of the length of the longest substring seen, and return the length at the end.

Using an Example

To start, I'll make an empty set called uniqueSub, and I'll initialize a variable longest which will keep track of the length of the longest substring seen. The inputted string will be "abbac", and I'll start by having two pointers, both on the first letter. j will be the blue circle, i will be the red circle, and the window, or substring, between the two working pointers, will be the opaque purple box in the background.

We will be keeping track of the letter circled by j, the blue circle. Since "a" is not in the uniqueSub set, we can add it to the set. Now, the longest substring is 1.

We'll now move over j, but keep i where it is--how long does this substring go? Again looking at the letter circled by j (blue), we can see that "b" is not in the uniqueSub set, so we can add it. The longest substring is now of length 2.

Now, we've moved j over again, and this time it's on another "b". "b" is already in the uniqueSub set. That means that the substring that started where i is located is no longer unique, so we need to move the window that we're checking over to the right. Therefore, the value at i should be removed from the uniqueSub, because we know that the substring starting at i is no longer unique. Now, uniqueSub just has "b" in it, but the longest value can stay at 2, since that's still the longest substring we've seen.

i has moved over one spot, and j has stayed at the same place. The substring we're currently working with isn't unique, so we should remove the value at i, therefore making uniqueSub empty, and keep moving i to the right. (Note: longest hasn't changed because it's keeping track of the longest unique substring seen so far. Until we find a unique substring longer than 2, we won't change this value.)

Now, i and j are circling the same letter "b", and uniqueSub is empty. We can add "b" to the uniqueSub set.

We've moved j one spot over, but kept i where it is. j is pointing at "a", which isn't in the uniqueSub set, so we can add it to the set.

We've moved j, the right pointer, over again. j is at "c", which is not in the uniqueSub set. We can add it, and now the size of the set is bigger than the previous longest substring we've seen, so we can update longest to be 3. Since j can't move to the right any further, we're at the end of the string, and our function will return 3.

Coding the Solution

The first thing we'll do is initiate a set and a few variables. uniqueSub is a set which will keep track of unique string characters. longest will keep track of the length of the longest unique substring seen. i and j are the two pointers which create a moving window, examining different parts of the string.

function lengthOfLongestSubstring(s) {
  let uniqueSub = new Set();
  let longest = 0;
  let i = 0;
  let j = 0;
  //...
}

Until either i or j hits the end of the string, we should continue checking it, so we can make a while loop. Also, we know we'll want to return the longest value at the end of the function, so we can include it at the bottom.

function lengthOfLongestSubstring(s) {
  let uniqueSub = new Set();
  let longest = 0;
  let i = 0;
  let j = 0;
  while (i < s.length && j < s.length) {
    //...
  }
  return longest;
}

Now, if the set does not already have the value at j (the right pointer), we can add that value to the set. We can use the .has and .add properties of sets here.

function lengthOfLongestSubstring(s) {
  let uniqueSub = new Set();
  let longest = 0;
  let i = 0;
  let j = 0;
  while (i < s.length && j < s.length) {
    if (!uniqueSub.has(s[j])) {
      uniqueSub.add(s[j]);
      //...
    } //...
  }
  return longest;
}

After we add the character at j to the set, we can calculate the longest value to equal whichever one is bigger--the previous longest value, or the size of the uniqueSub set. To do this, we can use Math.max, which returns the larger of the values. We also can move j over to the right.

function lengthOfLongestSubstring(s) {
  let uniqueSub = new Set();
  let longest = 0;
  let i = 0;
  let j = 0;
  while (i < s.length && j < s.length) {
    if (!uniqueSub.has(s[j])) {
      uniqueSub.add(s[j]);
      longest = Math.max(longest, uniqueSub.size);
      j++;
    } //...
  }
  return longest;
}

Finally, if uniqueSub already has the character that j is on, then we know the substring we've been working on is over, and we should move the window over to the right. That means that we need to delete the value at i from the set, and increment i. The reason that we're deleting the value at i is that we don't want to check future characters against it in the set any more.

function lengthOfLongestSubstring(s) {
  let uniqueSub = new Set();
  let longest = 0;
  let i = 0;
  let j = 0;
  while (i < s.length && j < s.length) {
    if (!uniqueSub.has(s[j])) {
      uniqueSub.add(s[j]);
      longest = Math.max(longest, uniqueSub.size);
      j++;
    } else {
      uniqueSub.delete(s[i]);
      i++;
    }
  }
  return longest;
}

I like this "windows" solution because it's pretty efficient in both space and time complexity, but I do think it's pretty difficult to wrap your head around the first few times you see it. Let me know in the comments if you've got any questions or alternate solutions!