Longest Substring Without Repeating Characters

You'll keep a sliding window with no repeated characters, and a set of what's inside it. You need strings and sets. Related chapter: sliding window.

1. The problem

You get a string. Return the length of its longest substring with no repeated character. A substring is a run of neighboring characters. Characters can be letters, digits, symbols, or spaces, and "a" and "A" are different. An empty string returns 0. This is LeetCode 3.

"abba" is the tricky one. When the second b arrives, you have to drop more than one character to get rid of the first b.

2. A correct baseline

def baseline(s):
    best=0
    for start in range(len(s)):
        seen=set()
        for end in range(start,len(s)):
            if s[end] in seen:
                break
            seen.add(s[end])
            best=max(best,end-start+1)
    return best

assert baseline('abcabcbb')==3
assert baseline('abba')==2
assert baseline('')==0

Each start scans forward until it hits a repeat. If any character could appear, that's O(n²) time: the work grows with the square of the string's length. LeetCode's strings use at most about 95 different characters, so each scan stops within 96 steps. That's still about 100 × n steps, and every start rebuilds its set from scratch. The set takes O(n) space in general.

The bottleneck. Each new start throws away its set and rebuilds almost the same one.

3. The observation

Take "abcabcbb". The window grows to abc. Then a second a arrives. Any substring that contains both a's has a repeat, so the window must now start after the first a. Drop characters from the left until the old a is gone: the window becomes bca.

So keep one window with no repeats, and a set of its characters. When the new character is already in the set, drop characters from the left until its older copy is gone. Then add the new one. This works because removing characters can never create a repeat, and adding characters can never remove one.

4. The solution and a trace

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        """Return a consecutive duplicate-free length; empty input gives 0."""
        seen=set()
        left=0
        best=0
        for right,char in enumerate(s):
            while char in seen:
                seen.remove(s[left])
                left+=1
            seen.add(char)  # Exactly the characters in the current valid window.
            best=max(best,right-left+1)
        return best

solve=Solution().lengthOfLongestSubstring
assert solve('abcabcbb')==3
assert solve('abba')==2
assert solve('')==0

Trace "abba":

5. Why it works

What stays true. The set holds exactly the window's characters, each once.

We never drop a start we need. left moves past a start only when the window from that start has a repeat. Adding more characters on the right can't fix a repeat, so that start is done for good.

We find the longest. After shrinking just enough, the window is the longest one with no repeats that ends at right. Taking the best over every right gives the longest overall.

6. Cost, edge cases, and failure

Cost. Each character enters the set once and leaves at most once. So despite the inner while, the total is O(n) time on average, growing in step with the string. The set takes O(n) space in the worst case.

Edge cases. Spaces count as characters. A substring has to be one unbroken run. A subsequence can skip characters, which makes a different problem.

Where it fails. Removing only one character isn't always enough:

assert len(set('ab'))==2
assert len(set('bb'))==1
assert solve('abba')==2  # At the second b, dropping only a leaves an invalid window.

import random
rng=random.Random(3)
for _ in range(1000):
    s=''.join(rng.choices('abAB 12!',k=rng.randrange(35)))
    assert solve(s)==baseline(s)