Sliding Window

Sliding window means you keep one contiguous slice of the array or string and update an aggregate (sum, counts, uniqueness) incrementally as the slice moves. Instead of rebuilding the slice from scratch each time ((O(n)) work per slice), each shift does (O(1)) amortized updates.

Deep dive: Sliding Window pattern.

Quick Identifier

• Topic: sliding-window
• Pattern: Fixed-size window (k consecutive elements), variable-size shortest/longest satisfying a constraint, or multi-pointer window variants.
• Core Question: Is the optimum always a contiguous subarray/substring, and does adding/removing one edge element change the answer in an easy-to-update way?

Fixed vs variable (the conceptual split)

Both rely on an incremental invariant: maintain counts or sums inside [left, right) so updating the window does not require a full rescan.

Variable-window templates (know which story you tell)

Both versions keep aggregates on [left, right] incremental; they differ when you shrink:

Shortest satisfying window (classic “minimum size subarray sum ≥ S” vibe):

After each inclusive step at right, while the aggregate already satisfies all constraints: record the current window span, increment left, and drop s[left] from the aggregate. Then continue expanding right. You only tighten while still valid, so every recorded window is feasible.

Longest valid window (classic “longest substring without repeating” vibe):

Grow right while the aggregate stays feasible. Whenever it breaks, repeatedly increment left (dropping edges) until the window becomes valid again; during expansions inside the feasible region record your best span.

Sketch on paper which phase you are describing before coding—mixing shortest vs longest control flow is the fastest way to introduce subtle bugs under time pressure.

Quick Sights

• Typical Time Complexity: (O(n)) for one pass windows—each index enters and leaves at most once.
• Typical Space Complexity: (O(u)) for frequency maps ((u) distinct characters or values).
• Core Mechanism: Update aggregate on [left, right] in (O(1)) amortized steps per boundary move.

Diagram

Recognition Cues

• “Longest substring / subarray with …”, “shortest with …”.
• Exactly k distinct characters, “at most k repeats”, permutation of another string.
• Consecutive buckets: fruit baskets, max frequency after k replacements, substring anagram counts.

Avoid sliding window when the answer is allowed to skip interior elements arbitrarily (might be two pointers or dynamic programming, not contiguous window).

Problem List

Build intuition in this order:

1. 003. Longest Substring Without Repeating Characters
2. 209. Minimum Size Subarray Sum
3. 567. Permutation in String
4. 438. Find All Anagrams in a String
5. 076. Minimum Window Substring
6. 424. Longest Repeating Character Replacement

Then specials like 239. Sliding Window Maximum (pair with monotonic deque in patterns) and dense variants in this folder.