IntermediateSliding Window
Variable windows: grow right, shrink left
“Longest substring with no repeats”: grow the window on the right, and when it breaks the rule, shrink from the left until it's valid again.
The idea
For “longest/shortest subarray or substring that satisfies X”, keep a window [left, right]. Move right forward every step. Whenever the window breaks the rule, move left forward until it's valid again. Track the best valid window.
Both pointers only ever move forward, so it's O(n) even though there's a loop inside a loop.
Worked example
Longest substring without repeats in “abcabcbb”
- a, ab, abc → length 3
- add a → “abca” repeats a → move left past the first a → “bca”
- add b → repeats b → shrink → “cab”; and so on. Best stays 3.
In code (Python)
def length_of_longest_substring(s):
last_seen = {}
left = best = 0
for right, ch in enumerate(s):
if ch in last_seen and last_seen[ch] >= left:
left = last_seen[ch] + 1 # jump past the repeat
last_seen[ch] = right
best = max(best, right - left + 1)
return bestO(n) time, O(k) space for k distinct characters.
How to spot it
- “longest / shortest / minimum window” + a condition on what's inside (no repeats, at most k distinct, sum ≥ target).
Common mistakes
- Moving left backwards when an old index is found: check `last_seen[ch] >= left`.
- Updating the best before the window is valid again.
Practise it
Go further
Up next for you · Beginner
“Have I seen this?” is a set →