Sliding window
A technique that keeps a running result for a contiguous range and updates it as the range moves, instead of recomputing every subarray.
Definition
A window is a range between two indices. A fixed window adds the element that enters and removes the one that leaves. A variable window grows on the right and shrinks from the left while it breaks a rule. Each element enters and leaves once, so the work is O(n). It needs a rule that changes in one direction as the window grows, which is why it works for non-negative sums but not with negative numbers.
In practice
The longest substring without repeating characters: grow the window, and when a character repeats, shrink from the left until it doesn't.
Learn it in context
Lessons that use this term.