Module 7
Sliding Window
Keep a window over a contiguous range and update it as it moves, adding what enters and removing what leaves, instead of recomputing from scratch.
Sliding window is two pointers specialised for contiguous ranges. The right pointer grows the window, the left pointer shrinks it, and a small summary (a sum, a count map) is updated in O(1) per move. Every element enters once and leaves once, so the whole scan is O(n).
There are two shapes. Fixed windows keep exactly k elements. Variable windows grow until a rule breaks, then shrink until it holds again; they answer "longest" and "shortest" questions. The module finishes with the "at most K" trick that turns "exactly K" into two easier windows.
Best after: Two Pointers, Hashing
Part 1
Learn the ideas
- 7.1Fixed-Size WindowsSlide a window of exactly k elements: add the element entering on the right, remove the one leaving on the left.12 min
- 7.2Variable Windows: Finding the LongestGrow the right edge every step; when the window breaks the rule, shrink the left edge until it's valid again. Record the size after fixing.15 min
- 7.3Variable Windows: Finding the ShortestFor "shortest window that satisfies X", grow until it's satisfied, then shrink while it stays satisfied, recording the size at each shrink.12 min
- 7.4Windows with Counts and the "At Most K" TrickKeep a count map of what's inside the window, track how many requirements are met, and turn "exactly K" into "at most K" minus "at most K − 1".15 min
Part 2
Solve the problems
In order of difficulty. Each one shows the pattern it teaches.
The fixed window template: add the entering element, subtract the leaving one.
The variable window for "longest": grow right, and when a character repeats, jump left past its previous position.
The "shortest" variant: shrink while the window is valid, recording its length each time.
A window is valid when (length − count of its most common letter) ≤ k; the max count never needs to decrease.
A fixed window the size of the pattern, compared by letter counts: anagram search in O(n).
The full shortest-window machine: need counts, a satisfied counter, grow until valid, shrink while valid.
Count "exactly K" as atMost(K) − atMost(K − 1), where each at-most count is a simple window.