Topic 4 of 20
Maintain a window over a sequence and update it incrementally instead of recomputing.
A sliding window is a contiguous range [left, right] that you move across an array or string, updating a small summary (a sum, a count, a frequency map) as elements enter and leave. Because each element enters and leaves the window at most once, problems that look like "check every subarray" (O(n²) or worse) drop to O(n).
There are two flavours. A fixed-size window of length k simply slides one step at a time. A variable window grows by moving right and shrinks by moving left whenever the window becomes invalid, so at every step you know the best valid window ending at right. Most "longest/shortest substring such that…" questions follow this template exactly.
Two advanced tricks round out the topic. To count subarrays with exactly k of something, compute at most k minus at most k−1. To get the maximum of every window in O(n), keep a monotonic deque of candidates. Master the template and a large family of Medium problems becomes routine.
Track the best buy so far; the gentlest window-style problem and extremely common.
The textbook fixed window: add the new element, drop the old one.
A window of size k kept in a set.
Sorting makes the best window contiguous.
The canonical variable window; one of the most-asked questions anywhere.
The 'window length − max frequency ≤ k' invariant is a classic insight.
Compare frequency maps incrementally as the window slides.
Same as Permutation in String but collecting every match.
Shrinks while the window is valid, the mirror of the longest-window template.
'At most k zeros' is the standard budget-constrained window.
Longest window with at most two distinct values, in disguise.
Counting subarrays ending at each right index; a key counting trick.
Introduces the 'exactly = at most − at most' trick.
The same trick applied to odd-number counts.
Maximise the ends by minimising the middle window, a neat reframing.
Sorting plus a window-sum budget check.
The flagship Hard window problem; a Meta and Google classic.
Introduces the monotonic deque for O(n) window maxima.
The hardest application of the at-most trick.
Slides in word-sized steps with a frequency map of words.