The invariant is the program
The hardest part of any sliding window is not the loop, it is the shrinking condition: the precise rule that says the current window is invalid and the left edge must move. Get this invariant right and the rest of the code is mechanical.
Stating the invariant
A clean window invariant describes what is always true between iterations, for example that the window contains no repeated character, or that a counter of distinct values stays within a limit. The shrinking loop exists solely to restore that invariant after each expansion breaks it.
Common shrinking rules
- At most k distinct values: contract while the distinct count exceeds k.
- No duplicates: contract while the entering element already sits in the window.
- Sum within a bound: contract while the running sum exceeds the bound.
A subtle ordering
You expand first, which may break the invariant, then shrink until it holds again, and only then record the answer. Recording before restoring the invariant is a frequent bug because the window may still be invalid.
Key idea
Define the window invariant precisely, let expansion temporarily break it, and shrink from the left until it holds again before recording any answer.