Sliding Window
A sliding window maintains a contiguous subarray (or substring) that satisfies a constraint, expanding the right pointer and shrinking the left pointer to stay valid in O(n).
Sliding window = a caterpillar inching forward. The head stretches right to eat more, the tail contracts left when the body gets too long. The caterpillar never goes backward.
Two patterns: (1) fixed-size window — move both pointers together (e.g., max sum subarray of size k); (2) variable-size window — expand right greedily, shrink left when constraint violated (e.g., longest substring without repeating characters, minimum window substring). The window state (a hash map, counter, or sum) is maintained incrementally rather than recomputed each time — this is what makes it O(n).
The key invariant: at all times, [left, right] represents a valid window, OR we are in the process of restoring validity by shrinking from left. Each element enters the window exactly once (right pointer advances) and leaves exactly once (left pointer advances) — giving O(n) total work. For problems with 'at most K distinct characters', track a frequency map and shrink when distinct count exceeds K. Monotonic deque (sliding window maximum) lets you get the max of the current window in O(1) amortized by maintaining a decreasing deque — O(n) overall.
Sliding window is my default for 'longest/shortest subarray/substring satisfying property X'. The template is: expand right to try to satisfy the constraint, shrink left when it's violated, and update the answer at each valid state. The O(n) argument is that each pointer moves at most n times. The subtle part is maintaining the window state incrementally — for character frequency, I use a hash map and a 'have/need' counter to avoid recomputing each time.
When shrinking the window from the left, you must correctly remove the element leaving the window from your state. Forgetting to decrement a counter or update a sum when left pointer advances is the most common bug. Also: the window boundaries are [left, right] inclusive — be consistent or you'll have off-by-one errors.