Run it
The window printed at every step, then the same input run against brute force so the operation counts sit side by side, and finally the abba case with the guard removed.
The sliding window
Expand the window rightwards; when a repeat appears, shrink from the left until it is gone.
O(n) time — each pointer moves forward at most n times — and O(k) space where k is the alphabet size.
Two details carry the correctness:
last[ch] >= left is essential. Without it, a character seen before the current window would drag left backwards. That is the "dvdf" case: at the second d, the first d is at index 0 but the window has already moved past it, so left must not jump back.
Jumping rather than stepping. left = last[ch] + 1 moves in one operation. Stepping one at a time while removing from a set is also O(n) overall and is easier to get subtly wrong.
The set-based variant
Some prefer the explicit shrink loop, which reads more like the general sliding-window template:
Same complexity. The while loop looks quadratic and is not: left only ever advances, so across the whole run it moves at most n times.
| | Index map | Set with shrink loop |
|---|
| Left pointer | Jumps | Steps |
| Subtle bug risk | The >= left check | None |
| Reads as the standard template | Less | More |
Either is acceptable. Offering the set version first and then the jump optimisation is a reasonable way to present it.
Why brute force is quadratic
Checking every substring is O(n²) substrings, each needing a uniqueness test — O(n³) naively, O(n²) with a set per start. The waste is that each restart throws away everything the previous one learned.
The window keeps it. When the right edge advances, the answer for the new window is derived from the old one instead of recomputed.
The jump, and the guard
Store each character's last index. When the character at the right edge has been seen, the left edge moves to seen[ch] + 1 — one past the previous occurrence, in a single step.
The guard is the subtle part: only jump if seen[ch] >= start. Without it, a character last seen before the current window drags the left edge backwards, shrinking the window for no reason. "abba" is the shortest input that exposes it: at the final a, the earlier a is already outside the window.
Cost, and what to say about space
Time is O(n): the right edge advances n times and the left edge only ever moves forwards, so both pointers together make at most 2n moves. Space is O(k) in the size of the alphabet, not O(n) — the map holds one entry per distinct character.
Interviewers like the space answer because most candidates say O(n).
Tracing the awkward cases
"pwwkew" with the index-map version:
| right | ch | last | left | Window | best |
|---|
| 0 | p | {p:0} | 0 | p | 1 |
| 1 | w | {p:0, w:1} | 0 | pw | 2 |
| 2 | w | {p:0, w:2} | 2 | w | 2 |
| 3 | k | … | 2 | wk | 2 |
| 4 | e | … | 2 | wke | 3 |
| 5 | w | w last at 2, ≥ left | 3 | kew | 3 |
"dvdf" — the case the >= left guard protects:
| right | ch | left before | Action | left after |
|---|
| 0 | d | 0 | New | 0 |
| 1 | v | 0 | New | 0 |
| 2 | d | 0 | last[d]=0 >= 0, jump | 1 |
| 3 | f | 1 | New | 1 |
Final window is "vdf", length 3. Without the guard, a later repeat of d would try to set left back to 1 when it had already advanced further — producing a window containing a duplicate and an answer that is too large.
Returning the substring
A common follow-up. Track where the best window started:
One extra variable, captured only when a new best is found. Note that best_start must be recorded at the moment best improves, not afterwards — left will keep moving.
| Problem | Condition maintained |
|---|
| No repeating characters | All distinct |
| At most k distinct characters | len(counts) <= k |
| Exactly k distinct | At most k, minus at most k−1 |
| Longest with at most one replacement | window_size - max_count <= 1 |
| Minimum window containing all of a pattern | All required counts satisfied |
| Anagram substring of a pattern | Counts match exactly |
The "at most k distinct" variant is the natural generalisation — this problem is the k = window-size case — and it uses a count dictionary rather than a set, shrinking while the number of distinct characters exceeds k.
The exactly k trick is worth knowing: "exactly k" equals "at most k" minus "at most k−1". Computing two at-most windows is easier than maintaining an exactly-k invariant directly.
The minimum window variant inverts the shrink condition: shrink while the window is still valid, recording before each shrink, because the goal is the smallest satisfying window rather than the largest. Getting that inversion wrong is the most common sliding-window error, and the symptom is an answer consistently too long or too short.
What it is testing
Do you recognise a sliding window? "Longest contiguous run satisfying a condition" is the signature.
Do you get O(n)? The nested while looks quadratic; explaining that each pointer advances at most n times is part of the answer.
Do you handle the stale-index case? "dvdf" is in every test suite for this problem.
Do you know it is contiguous? Answering 4 for "pwwkew" means you solved the subsequence problem instead.
Can you state the space complexity? O(min(n, k)) — bounded by the alphabet, not the string.
Recap in one screen
- Expand the window rightwards; on a repeat, move the left edge past the previous occurrence.
- Check
last[ch] >= left or the left pointer moves backwards on characters outside the window. - O(n) time despite the inner loop, because both pointers only advance; O(k) space for the alphabet.
- Substring means contiguous —
"pwwkew" answers 3, not 4. - The family generalises to at-most-k distinct, minimum window, and anagram substrings, with the shrink condition inverted for minimum problems.