Sliding Window

A contiguous window over an array or string that expands its right edge and shrinks its left edge based on a condition, instead of recomputing from scratch — turning an O(n²)/O(n³) brute-force scan into O(n). Fixed-size windows have a given length k; variable-size windows grow and shrink based on a validity condition, often paired with the have/need hash-map logic from Hash Map. Monotonic deque windows are their own sub-pattern, covered separately under Queue and Monotonic Deque.

Sub-patterns

• A — Fixed-Size Aggregate Window. Window length k is given up front; slide it and update the running aggregate incrementally.
• B — Variable-Size Shrinkable Window. Expand the right edge, then shrink the left edge as far as possible while a condition still holds.
• C — Variable-Size Expandable Window. Expand until a condition is met, tracking the best window found so far.
• D — Frequency-Matching Window with a Hash Map. A have/need pair of counters tracks whether the window currently satisfies a target frequency profile.

Practice set (13)

• Easy — Contains Duplicate II, Maximum Average Subarray I
• Medium — Longest Substring Without Repeating Characters, Longest Repeating Character Replacement, Permutation in String, Fruit Into Baskets, Max Consecutive Ones III, Find All Anagrams in a String, Subarray Product Less Than K, Longest Subarray of 1s After Deleting One Element, Frequency of the Most Frequent Element
• Hard — Minimum Window Substring (already solved under Two Pointers), Substring with Concatenation of All Words