Sliding window

What & when

A contiguous span [left, right] that grows on the right and shrinks on the left, so every subarray/substring is examined once instead of re-scanned. Reach for it on contiguous subarray / substring prompts asking for the longest / shortest / max-sum span under a condition — a given fixed length K (the fixed-window case), or a constraint that tightens or relaxes as the span moves, like “at most K distinct”, “no repeats”, or “sum ≥ target” (the variable-window case). Transformation: contiguity lets the window’s aggregate update incrementally — add the entering element, drop the leaving one — instead of rescanning. Complexity lever: each index enters and leaves the window at most once, so a nested O(n·k) rescan collapses to a single O(n) pass. Part of the DSA patterns hub.

Skeleton

The variable-window template. state is whatever summary makes the validity test O(1) — a running sum, a char-count map, a distinct counter.

def sliding_window(s):
    state = new_state()                # the window's running summary
    left = best = 0
    for right, x in enumerate(s):
        add(state, x)                  # element entering on the right
        while must_shrink(state, x):   # ← DECIDE: shrink test
            remove(state, s[left])     # ← DECIDE: undo the leaver
            left += 1
        best = record(best, left, right)   # ← DECIDE: what to record
    return best

Solving a problem = filling three blanks: the shrink test (must_shrink — when is the window invalid?), the undo when left advances (remove), and what you record (record — longest, shortest, or a count). A fixed-size window drops the while for a single if right - left + 1 > k eviction.

Walkthrough

Longest substring without repeating characters on "abcabcbb". The band W is the window; when a repeat enters on the right, left advances until the window is unique again. Best length seen stays 3.

Problems

names link to my write-ups as I solve them — the list is the curriculum, the links are progress.

When it fails

• You need an aggregate over an arbitrary range, not a contiguous grow/shrink — precompute a prefix-sum and subtract two endpoints instead.
• The window must track an extreme by value, not a sum or count (e.g. sliding window maximum) — a plain window can’t; use a monotonic-queue.
• There’s no monotone “adding hurts / removing helps” relationship — then shrinking left isn’t justified and the window never converges.

Related

• Two pointers — a sliding window is the same-direction two-pointer case; left and right both march forward.
• monotonic-queue — the upgrade when the window must report a max/min by value.
• Binary search — when a feasible window length is monotone, binary-search the length and validate each guess with a window.
• In production: a window is a bounded context over a stream — LLM context / token-budget management (admit tokens on the right, evict the oldest on the left to stay under budget, gated by a maintained aggregate), and sliding-window rate limiters over request timestamps.

Pattern DNA