When to reach for it
You have a contiguous subarray/substring problem and a brute force that
recomputes some aggregate (sum, count, max, distinct-count) for every window.
The window's answer for position i+1 is almost the same as for i — so
instead of recomputing, you slide: add the entering element, remove the
leaving one.
Signal phrases: "longest/shortest substring/subarray", "at most K", "exactly K", "maximum sum of size k", "contains all characters of…".
Two flavours
- Fixed-size window — window width is given (
k). Slide one step at a time. - Variable-size window — grow
rightgreedily; shrinkleftwhile a constraint is violated. The answer is usually the max/min window seen.
# Variable window: longest substring with at most K distinct characters
from collections import defaultdict
def longest_k_distinct(s: str, k: int) -> int:
count = defaultdict(int)
left = best = 0
for right, ch in enumerate(s):
count[ch] += 1
while len(count) > k: # constraint violated → shrink
count[s[left]] -= 1
if count[s[left]] == 0:
del count[s[left]]
left += 1
best = max(best, right - left + 1)
return best
State the loop invariant out loud in the interview: "the window [left, right]
is always valid after the inner while-loop." Each index enters once and leaves
once, so the two pointers move a total of 2n steps → O(n) even with the
nested loop.
Watch it run
The "add one, drop one" trick in motion — the window never recomputes its
sum from scratch. Change k and watch the work per slide stay O(1).
1/10Build the first window of size 3 by adding its elements once: sum = 15.
Complexity
| Brute force | Sliding window | |
|---|---|---|
| Time | O(n·k) / O(n²) | O(n) |
| Space | O(1) | O(k) for the window's bookkeeping |
Because the window only ever holds ≤ K+1 distinct keys — not the whole input — a sliding window is already a bounded-memory, one-pass algorithm, so it streams as-is. When the follow-up pushes further ("count distinct items, or the top-K, over an unbounded stream"), exact state stops fitting and you reach for streaming algorithms & sketches.
Practice set
- Maximum sum subarray of size K — fixed window
- Longest substring without repeating characters — variable, shrink on dupe
- Minimum window substring — variable, need-map + formed counter
- Fruit into baskets — at most 2 distinct
- Permutation in string / find all anagrams — fixed window + frequency match
Practice — climb the ladder
The trigger: "longest/shortest/count of CONTIGUOUS subarray or substring satisfying X". Fixed size slides; variable size grows right, shrinks left.
Climb in order — every rung assumes the one above it. Solve on LeetCode, then tick it here; progress is saved on this device.
Warm-up
fixed-size windows firstFixed window — add the entering element, subtract the leaving one; no recompute.
Window in disguise — running minimum behind you IS the left edge.
Core
variable windows with a validity conditionTHE variable window — grow right, shrink left until valid again; set tracks membership.
Validity = window size − max frequency ≤ k; subtler invariant, same skeleton.
- Permutation in StringMedium
Fixed window + frequency match — two counters kept in sync as it slides.
- Max Consecutive Ones IIIMedium
Budget-based validity (k zeros allowed) — spend entering, refund leaving.
- Fruit Into BasketsMedium
At most two distinct — the at-most-K family in its friendliest form.
Stretch
the boss fightsShrink to the SMALLEST valid window — need/have counters; the canonical hard window.
Monotonic deque carrying the max — windows + stacks-and-queues combined.