How the sliding window solves Longest Substring Without Repeats

Given the string "abcabcbb", the longest run with no repeated character is "abc", so the answer is 3. Feed it "bbbbb" and you get 1. Feed it "pwwkew" and the answer is "wke", which is 3, not "pwke", because that skips a character and stops being a substring. That is LeetCode 3, and it turns up in phone screens at Amazon, Meta, Bloomberg, and a long tail of startups because it sorts people who reach for the sliding window from people who don’t.

The trap is that the problem sounds like it wants you to compare substrings against each other. It doesn’t. You never need to hold two windows at once, and the moment you see that, the obvious quadratic idea collapses into a single pass over the string.

Why checking every substring is the wrong instinct

The brute-force reading goes like this: pick every start index, extend to every end index, and test whether the slice has a duplicate. For a string of length n there are about n²/2 substrings, and each uniqueness check can cost another n, so you land near O(n³). Keep a running set as you extend a fixed start and you shave that to O(n²), but you are still re-scanning characters you already cleared every time the start moves.

An interviewer will usually let you say the brute force out loud, then go quiet. The silence is the hint. What are you recomputing? Every time the start slides forward by one, you throw away everything you just learned about the characters in between. The window keeps that work instead of discarding it.

One window, two pointers

Hold a window over the string with two indices, left and right. The property you maintain is an invariant: every character inside [left, right] is distinct. Walk right forward one step at a time. Whenever the incoming character already sits in the window, pull left forward until the window is clean again. The answer is the widest the window ever gets.

This is linear because both pointers only ever move right, and neither runs past n. Each character enters the window once when right crosses it and leaves at most once when left crosses it. That caps the total pointer movement at 2n, no matter how the string is arranged.

The set version, and the trace that sells it

The most readable version keeps the window’s characters in a hash set. When right meets a character already in the set, drop characters from the left until the repeat is gone, then add the new one.

def length_of_longest_substring(s: str) -> int:
    seen = set()
    left = 0
    best = 0
    for right, ch in enumerate(s):
        while ch in seen:
            seen.remove(s[left])
            left += 1
        seen.add(ch)
        best = max(best, right - left + 1)
    return best

Trace "pwwkew". The window grows to "pw", then right lands on the second w. The inner loop removes p and the first w, leaving left on the second w, so the window is now just "w". It grows to "wke" (width 3), the next w forces another shrink, and the final run is "kew", again width 3. The best it ever recorded is 3. That inner while looks like it might make the whole thing quadratic, but it can’t: left advances at most n times across the entire run, so all the shrinking together is bounded by n.

Time is O(n). Space is O(min(n, k)), where k is the alphabet size, because the set never holds more distinct characters than the charset allows. For plain ASCII that ceiling is 128, and the window physically cannot contain more unique characters than that.

The map version that jumps instead of crawls

The set version nudges left forward one character at a time. You can skip the crawl by recording where each character was last seen and jumping left straight past it. Map every character to its most recent index; on a repeat, move left to one position after that index.

def length_of_longest_substring(s: str) -> int:
    last = {}
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1
        last[ch] = right
        best = max(best, right - left + 1)
    return best

The entire game lives in the last[ch] >= left guard, and it is the line people drop under pressure. Run "abba" without it. You reach the final a, look up its last index of 0, and set left = 1, which drags the left edge backward past the b you already cleared. The width comes out wrong and the count inflates. The guard says jump only when the previous sighting is actually still inside the window; a stale index sitting behind left gets ignored. With the guard in place, "abba" returns 2, which is correct.

Set or map: which one to write on the whiteboard

Both are O(n) time and O(min(n, k)) space, so the pick comes down to clarity and to what the interviewer wants to watch you reason about.

Aspect	Set with shrink loop	Map of last index
How left moves	One step per removed character	Jumps past the repeat
Passes over the string	Amortized single pass	Strict single pass
Ease of explaining	High, the invariant is visible	Needs the stale-index caveat
Where it breaks	Forgetting to re-add after shrinking	Dropping the >= left guard
Returning the substring	Save best left on each update	Same

When you are talking through the solution live, the set version is easier to defend because the invariant is right there in the loop. The map version reads faster once it exists, but it hides its correctness inside one comparison, which is exactly the spot a sharp interviewer will poke at.

What the follow-up usually is

Most interviewers won’t stop at the length. A frequent next ask is to return the substring itself rather than its size, which means saving the best left whenever you update best and slicing at the end. Another is handling Unicode instead of ASCII, which mostly means not assuming a fixed 128-slot table and staying with a hash map. The bigger one, the generalization the window was really building toward, is the longest substring with at most k distinct characters: same two pointers, but the shrink condition becomes “more than k distinct” instead of “any repeat at all”. That is LeetCode 340, and getting there smoothly is the signal that you learned the pattern rather than memorizing one answer.

If someone pushes on the constant factor, there is a fixed-array variant worth having ready. Swap the hash map for an int[128] indexed by character code, storing last-seen index plus one so that zero reads as unseen. Identical logic, no hashing cost, and it reads cleanly in C++ or Java where a map lookup carries real weight.

Where people actually lose the round

The failure is almost never the big idea. It is the small mechanics. Off-by-one on the width, since right - left + 1 counts inclusive endpoints and tired candidates write right - left. Updating the last-seen index only on repeats instead of on every character. Resetting the set rather than shrinking it, which quietly drags the whole solution back to O(n²). And the >= left guard, one more time, because "abba" and "tmmzuxt" are the exact strings interviewers keep in a back pocket to break a careless jump.

Get the window invariant fixed in your head before you write anything, put down the set version if you want something you can narrate line by line, and reach for the map only when you can also say out loud why a character last seen at index 0 stops mattering once left has passed index 3.