Sliding Window

AI Generated

A window [l, r] over a contiguous run. Extend r to take more in, shrink l while the window is invalid. Every index enters and leaves at most once, so the whole thing is O(n) despite the nested loop.

• Variable size — grow until the constraint breaks, shrink until it holds again, record the best window seen (longest substring without repeating characters, minimum window substring).
• Fixed size — slide by one: add the entering element, remove the leaving one (permutation in string).

The trick that makes it O(n) rather than O(n·k) is keeping an incremental summary of the window — a count map, a running sum, a max frequency — so checking validity is O(1) instead of a rescan. A deque extends the same idea to the window's maximum.

It only works when the answer is contiguous and shrinking can never hurt.