LeetCode 3: Longest Substring Without Repeating Characters

Problem 3. Longest Substring without Repeating Characters

Begin by defining the stack variable and max variable.

let stack = new Set()
let max = 0

Using a for loop we can begin adding each element from the input string. At the same time, we want to keep track of the longest substring in the max variable by comparing the current max size and the size of the stack up until that point.

Our full code, so far, would look like this:

var lengthOfLongestSubstring = function(s) {
  let stack = new Set()
  let max = 0

  for (let i=0; i<s.length; i++) {
    stack.add(s[i])
    max = Math.max(max, stack.size)
  }
return max
}

That's a good starting point, but now we need to account for any repeating characters.

Once we get to the third index, you can see that the stack would be:

stack = [a,b,c,c]

This is not what we want because the problem is asking for the longest substring without repeating characters.

To resolve this we need to delete all of the elements in our current stack until there are no repeated characters and then continue the logic we coded above (adding and keeping track of the max).

In order to do this we need to add another variable called left. Our variables can be updated to this:

  let stack = new Set()
  let max = 0
  let left = 0

This left variable is going to point to an element in the string that we delete in our stack. Currently:

left = 0, so s[left] = 'a'.

Using a while loop, we can add logic to delete all of the elements preceding the repeated character. In our case, since our stack = [a,b,c,c] we want to delete stack = [a,b,c] and be left with stack = [c].

The while loop looks like this:

  while (stack.has(s[i])) {
    stack.delete(s[left])
    left++
  }

This will pause at the current i-th iteration in our for loop and execute until true.

Looking at the purple section in the image we can see we're paused at i=3 because our current stack now has a repeated character 'c'. Whenever a repeated character occurs our code will enter the while loop and execute the commands (delete and left++) until false.

It's important to understand that the while loop will keep performing the (delete and left++) commands until the stack no longer has a condition where stack.has(s[i]).

We'll come back to this. Let's run it back to the beginning.

Here is our full code:

var lengthOfLongestSubstring = function(s) {
  let stack = new Set()
  let max = 0

  for (let i=0; i<s.length; i++) {
    while (stack.has(s[i])) {
      stack.delete(s[left])
      left++
    }
    stack.add(s[i])
    max = Math.max(max, stack.size)
  }
return max
}

Take note of where we've placed our while loop. The reason why we we're able to iterate from i=0 to i=3 without entering the while loop is because stack.has(s[i]) was never true.

At i=0, does stack have s[0] or ('a')? No, so we add 'a' to the stack and our for loop goes to i=1. Now our stack=[a].
At i=1, does our stack have s[1] or ('b')? No, so we add 'b' to the stack and our for loop goes to i=2. Now our stack=[a,b].
At i=2, does our stack have s[2] or ('c')? No, so we add 'c' to the stack and our for loop goes to i=3. Now our stack=[a,b,c].
At i=3, does our stack have s[3] or ('c')? YES, and this will trigger our while loop.

Once we have triggered the while loop, as we mentioned above it will start to delete elements from the stack and add 1 to the left variable.

Let's take a closer look at i=3.

Well, after i=2, our stack=[a,b,c]. Now, looking at when i=3, our while loop has checked that, yes, the stack has s[3] or 'c' and begins to delete and add one to left.

what does that look like?

stack.delete(s[left])

This will delete s[left], which currently left=0.
So, we delete s[0] or 'a'.
Then we add one to left.
left=1.

Ok, looking at the code we continue down to stack.add(s[i]) and update the max variable, right? NO!

Because we're in a while loop, we don't exit until the condition stack.has(s[i]) is false. After updating the previous sequence we see that stack=[b,c], left=1 and s[i]= 'c' since we're still paused at i=3.

The while loop continues checking if our stack has 'c'. It does, so we delete s[left], which is now s[1] from the stack and iterate left by 1.
Now our stack=[c] and left=2.

Again, the while loop checks if our stack has 'c'. It does, so we delete s[left], which is now s[2] from the stack and iterate left by 1.
Now our stack=[] and left=3.

Again, the while loop checks if our stack has 'c'. It doesn't because our current stack is empty. In the code, we exit the while loop and execute the next part of the code which is:

  stack.add(s[i])
  max = Math.max(max, stack.size)

So, we add s[i] or 'c' to our stack and calculate the max. Math.max takes the bigger value between max, currently 3 from stack=[a,b,c], and the current stack.size, which is 1.

Now, stack=[c] and max=3

This concludes i=3 and the for loop continues to i=4.

At i=0, does stack have s[4] or ('a')? No, so we add 'a' to the stack and our for loop goes to i=5. Now our stack=[c,a] and we can see that max = Math.max(3,2), 2 being the stack.size of stack=[c,a]. So, still max=3.

Now, stack=[c,a] and max=3

At this point you should be able to follow the remainder of the for loop. We add another element at i=5 and enter the while loop at i=6.

When our for loop ends we check the max value and see that it's 3, which indicates that the longest substring our code found was length 3. In this case, the strings equal to 3 were [a,b,c] and [c,a,b] but the question was not asking for which strings, only the longest length.

The time complexity of this function is O(n), where n is the length of the input string s.

The reason for this is that the function iterates through each character in the string once using a for loop. Within the loop, it performs a constant number of operations, which include set operations (adding, deleting, and checking for membership in the set) and arithmetic operations (comparing and taking the maximum).

The space complexity of this function is O(min(n,m)), where n is the length of the input string s and m is the size of the character set (i.e., the number of distinct characters in s).

The reason for this is that the function uses a set stack to store the characters in the current substring it is considering. The size of the set can be at most the size of the character set, which is O(m). In the worst case, where all characters in the input string are distinct, the size of the set would be equal to n.

In addition to the set, the function also uses a constant amount of additional space O(1) to store variables such as left and max. However, this does not affect the space complexity since it's a constant.

Therefore, the space complexity of the function is O(min(n,m)), since the overall space used by the function is dominated by the size of the set, which is the minimum of n and m.

The best case scenario for this function is when the input string s contains only one character or is empty. In this case, the for loop will execute only once, and the while loop will not execute at all, resulting in a time complexity of O(1) and a space complexity of O(1).

lengthOfLongestSubstring('a') // returns 1
lengthOfLongestSubstring('') // returns 0

The worst case scenario of the function is time complexity O(n) and space complexity O(m), where n is the length of the input string s and m is the stack size of all unique characters.

lengthOfLongestSubstring("abcdefghijklmnopqrstuvwxyz") // In this case, the input string contains all unique characters, and the `stack` set will have to accommodate all characters of the input string. Therefore, the worst case space complexity is O(n), not O(m).

Hope this was helpful. Please leave a comment if anything looks incorrect or if you have any questions.

Happy coding!