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 important. 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.