1Understand
The idea
Grow the window by moving the right end one step at a time. Whenever the window breaks the rule, shrink it from the left with a while loop until it is valid again, then record the answer. Each element enters and leaves the window at most once, so the whole scan is O(n). It works when shrinking a window can only make it "more valid".
Intuition
The window is a contiguous slice [left, right] that you grow and shrink. Grow by moving right. Whenever the slice breaks the rule, shrink from left with a while loop until it is valid again. Each index enters and leaves at most once, so the whole scan stays O(n).
This works when shrinking can only make the window "more valid" (non-negative sums, "at most K distinct", no-repeat characters). Negative numbers break that monotonicity, switch to prefix sums.
Update the answer only when the window is valid. Using if instead of while when shrinking leaves the window illegal and under-counts.
What you will be able to do
- State the window invariant
- Shrink with while, not if
When to use it
- Longest / shortest subarray or substring that satisfies a condition
- "At most K distinct"
- Contiguous and all values non-negative
2See it
Walkthrough
Longest substring without repeats
s = "abcabcbb", grow right, shrink left with while until the window is valid again.
1 / 5
Start with left = right = 0. Window "a" is valid. best = 1.
Live template
Line 6 active
Complexity: time O(n), space O(k)
Time is O(n) because each pointer moves forward only. Space is O(k) for the alphabet or distinct keys you track. Prefer this over O(n²) checked substrings. If the condition is not monotone in window size, variable windows do not apply.
Read the walkthrough as text
Longest substring without repeating characters. s = "abcabcbb".
rightwalks each character; keep a count (or last-seen index) of what is inside the window.- When a duplicate appears, advance
leftuntil that character appears only once. - After the window is valid, update
best = max(best, right - left + 1).
Trace: windows grow a, ab, abc, then shrink before the second a, and so on. The answer is 3 ("abc").
In code:
left = 0; best = 0; count = {}for right, ch in enumerate(s):count[ch] = count.get(ch, 0) + 1while count[ch] > 1:count[s[left]] -= 1left += 1best = max(best, right - left + 1)
3Recognise it
Kinds of problems (8)
Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.
Longest window without repeats
Example. Longest substring with all unique characters.
How. Grow right; when a duplicate enters, shrink left with while until the window is valid again; track best length.
At most K distinct
Example. Longest substring that uses at most K different characters.
How. Same grow/shrink loop; the validity rule is “distinct count ≤ K” instead of “no duplicates”.
Shortest window with sum ≥ target
Example. Minimal length subarray whose sum is at least target (positives).
How. Grow right to increase the sum; while the sum still meets the target, shrink left and update the best length.
Minimum window substring
Example. Smallest window of s that covers every character of t (with counts).
How. Track how many required counts are satisfied; shrink left greedily once the window is complete.
Exactly K = at most K minus at most K−1
Example. Number of substrings with exactly K distinct characters.
How. Count windows with ≤ K distinct, subtract those with ≤ K, 1; the difference is exactly K.
Valid while length − max count ≤ k (character replacement)
Example. Longest substring you can make uniform with at most k replacements.
How. Window stays valid while window length − highest frequency ≤ k; shrink left when that breaks.
Complement window (remove from both ends)
Example. Shortest removal from ends so the middle meets a condition.
How. Often rewritten as a longest valid middle window, same variable-window scan with a different score.
Counting subarrays from run lengths
Example. Count subarrays of identical characters or similar runs.
How. When the window is a pure run of length L, it contributes L (or L·(L+1)/2) new subarrays ending at right.
Common mistakes
Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.
Shrinks only once
Why it happens. One shrink often looks enough in the first example, so `if` feels sufficient.
How it fails. Window still contains two copies of a character after a single left += 1; you record an invalid length and under-count later.
Fix. Shrink with `while not valid`, not `if`. Left may need to move more than once before the window is legal again.
Stale counts
Why it happens. Moving left without updating the frequency map leaves the validity check lying.
How it fails. You left += 1 past a character but never decrement its count; the window looks “too full” forever and you shrink into emptiness.
Fix. Every time left advances, remove a[left] from the window state (count, sum, set) in the same breath.
Answer updated at the wrong time
Why it happens. It is tempting to update `best` as soon as right moves, before the while-shrink finishes.
How it fails. You set best = right - left + 1 while the window still has a duplicate; the reported length is illegal.
Fix. Record the answer only after the window is valid again, after the while loop, not before.
Left pointer moves back
Why it happens. A bug fix tries to “jump” left to an old index from a map instead of only shrinking with left += 1.
How it fails. left was 5; you set left = 2 because an old index says so, elements 2..4 are counted twice and the window breaks.
Fix. Left only moves forward: while invalid, remove a[left] and left += 1. Maps store metadata, not backward jumps.
4Check yourself
Concept check
A short quiz on this lesson before you practise. Optional, and it does not gate coding.
Ready to practise?
Mastery comes from solving. The lesson is optional context.