There is a version of the sliding window that people learn as a shape: two indices, move the right one, sometimes move the left one, track a best answer. It works on the easy problems and falls apart on the rest — not because the shape is wrong, but because the shape is not the algorithm. The invariant is.
Write the sentence first
Before any code, finish this sentence: between iterations, the window always ___. For the classic problems that sentence is short and specific.
- →Longest substring without repeating characters: the window contains no duplicate character.
- →Longest substring with at most K distinct: the window contains at most K distinct characters.
- →Minimum window substring: the window contains every required character, with multiplicity.
- →Maximum sum subarray of size K: the window has exactly K elements.
Once you have that sentence, the loop writes itself: expand on the right unconditionally, then shrink from the left while the sentence is false. Not once — while.
The bug this prevents
The most common sliding-window bug is shrinking exactly once per iteration, out of habit, using an if instead of a while.
On many inputs a single shrink is enough, so this passes the samples. It breaks the moment one expansion pushes the window two or more characters out of legality — which happens as soon as the alphabet is small and the string is adversarial.
Expand with a for. Shrink with a while. If your shrink is an if, you have assumed one expansion can only break the invariant by one unit — and you almost never checked whether that is true.
The invariant also tells you where to record the answer
This is the part people miss. If the invariant is a validity condition — 'the window is legal' — then the window is legal after the shrink, so record the answer after the shrink. If the invariant is a coverage condition — 'the window contains everything required' — then the window is valid before you shrink it, and shrinking is what makes it minimal, so record inside the shrink loop.
Keep a counter, not a comparison
For coverage problems, do not compare two dictionaries on every move — that is O(alphabet) per step and it turns a linear solution into something that times out. Track a single integer: how many required characters are currently satisfied. Increment it when a count reaches its requirement, decrement it when it drops below. The check becomes an integer comparison.
A checklist
- →State the invariant in one sentence, in words, before writing code.
- →Expand unconditionally on the right.
- →Shrink with while, never if.
- →Decide from the invariant whether the answer is recorded before or after the shrink.
- →Replace dictionary comparisons with a satisfied-count integer.
Reading about a pattern is not the same as producing it under time pressure. The problems that drill this are in the curriculum, in order.