Problem Statement in English

You’re given a string s. Your task is to find the longest substring in s that has no repeating characters.

Approach

The naive bruteforce approach of using a nested loop is straight forward, and we’re not going to cover that. We’ll cover the linear time approach that uses the Sliding Window technique with a dynamic window size.

The way we do this is by maintaining 2 pointers. A left pointer, and a right pointer. The left pointer points to the beginning of the current window we’re interested in, and the right one maintains the end of it.

We move the right pointer forward while a certain condition is met, and otherwise, we move the left pointer forward.

In particular, as we move the right pointer forward we add every character we see to a Set - unless it’s already in the Set, in which case, we’ve got outselves a duplicate!

So that’s the first part done. What do we do when we encounter a duplicate? Well, let’s think about what it means first. If the right pointer points at something that’s already been seen, that means it’s occurred before the right pointer, and after, or at the left pointer.

Our duplicate free string now has duplicates in it, and so, we move the left pointer forward until we don’t have that duplicate anymore.

Solution in Python


class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        ans = 0

        leftPtr = 0

        charSet = set()

        for rightPtr in range(len(s)):
            while s[rightPtr] in charSet:
                charSet.discard(s[leftPtr])
                leftPtr += 1
            ans = max(ans, rightPtr - leftPtr + 1)
            charSet.add(s[rightPtr])

        return ans

Complexity

  • Time: $O(n)$

Since we process $n$ characters at most.

  • Space: $O(n)$

Since we store upto $n$ elements at most in the Set.

And we are done.