STEP 10 · SLIDING WINDOW · SLIDING WINDOW · MEDIUM

Longest Substring Without Repeating Characters

WHAT IT SAYS

Given a string, find the length of the longest stretch of consecutive characters that contains no duplicates.

WHAT IT'S REALLY ASKING

"When a character repeats, it doesn't just kill the start you're sitting on — it kills a whole block of starts at once. Exactly which ones? And once you've abandoned them, can the left edge ever be forced backwards again?"

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Fix a start, walk until it breaks

O(n²) time, O(min(n, Σ)) space

Pick a start i. Walk right, keeping a set of what you've seen, stopping the moment a character repeats. Record the length, then do it all again from i + 1. Every substring gets considered, so correctness is not in doubt.

WHERE THE WORK IS WASTED — Restarting at i + 1 throws away a proof you already own. If the walk from i died at position r because s[r] repeats a character last seen at p, then the walk from i + 1 re-verifies s[i+1..r-1] — characters you literally just proved distinct — only to die at the same r, on the same pair. So does i + 2, and every start up to p. You rerun the same scan to rediscover the same collision, over and over.

KEY OBSERVATION — THE UNLOCKlink

A repeat condemns every start at or before its twin.

You're at right end r, the character is c, and c last appeared at p (with p at or after your current left edge). Take any start i ≤ p. The window [i..r] contains both copies of c, so it is invalid — not 'probably bad', provably dead. And it stays dead for every right end past r, since windows only grow rightward and can never shed the pair. The surviving starts at right end r are exactly p+1 through r: one hop, no search. Now the half that makes it cheap. Validity here is hereditary: chop characters off the left of a duplicate-free window and it's still duplicate-free. So if [l..r+1] is clean, [l..r] was clean too — meaning the leftmost surviving start for r+1 can never sit to the left of the leftmost surviving start for r. The left edge is monotone. It advances or it stays; it never rewinds. Two pointers, each crossing the string once.

Left crawls, right walks

O(n) time, O(min(n, Σ)) space

The right end steps forward one character at a time, adding to a set. When the incoming character is already in the set, advance the left edge — evicting as you go — until the offending duplicate is gone, then record the window length. The inner loop looks nested, but every index enters the window once and leaves at most once, so total pointer travel is 2n.

Skip the crawl: remember where each character last lived

O(n) time, single pass, O(min(n, Σ)) space

Replace the set with a map: last[c] = most recent index of c. On reading c at r, the new left edge is max(left, last[c] + 1) — the condemnation applied in one hop instead of a crawl. That max is the entire subtlety: if last[c] sits behind the left edge, that copy was condemned and evicted long ago, and obeying it blindly would drag left backwards — which monotonicity says can never be necessary.

WHAT YOU TRADED — You trade O(Σ) memory for the linear scan — but the real currency is a property, not a data structure: 'no repeats' is hereditary, so shrinking a valid window keeps it valid, which is the only reason the left edge is allowed to be monotone. Remove that heredity — ask instead for the longest subarray summing to exactly k with negatives allowed — and the left edge can be forced backwards, and the sliding window collapses into brute force wearing a costume.

WATCH THE IDEA RUN

window 0

best 0

left edge (never rewinds) 0

Right walks forward exactly once. The only real question is where the left edge gets dragged to — and whether it ever has to come back.

step 1 / 11

THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

Doomed-Start Window

YOU'LL SEE IT AGAIN WHEN

You want the longest (or shortest) contiguous stretch satisfying a property that is monotone in length: shrinking a valid window keeps it valid.
When a candidate window breaks, you can point at the exact element that broke it — so you know precisely which starts died, not merely that some did.
Brute force would restart each candidate start from scratch and re-verify a prefix it already checked.
The property can be updated in O(1) as one element enters or leaves the window.

SAME BLUEPRINT, DIFFERENT PROBLEM

Longest Repeating Character ReplacementFruit Into BasketsLongest Substring with At Most K Distinct CharactersMinimum Window Substring

The bar isn't "solved it once." It's "could rebuild it from the observation."