On this page

Sliding Window: Fixed, Variable & With Counters

A sliding window is a contiguous range [left, right] of an array or string that you move from left to right while maintaining some summary of its contents — a sum, a count of distinct values, a frequency table. The summary is updated incrementally when an element enters at the right or leaves at the left, so each element is touched a constant number of times and the whole problem runs in . The pattern answers the family of questions that begin "find the longest / shortest / number of contiguous subarrays such that…", and it is the single most frequently tested technique on arrays and strings after plain iteration.

Lesson position: Module 1 · Linear Data Structures · previous: Two Pointers · next: Prefix Sums & Difference Arrays · course map.

Why this exists

There are contiguous subarrays of an array of length . Any question about "the best subarray" — longest with a property, shortest with a property, how many have a property — has a brute-force answer that enumerates all of them and evaluates each. If evaluating costs (summing the elements, checking for duplicates), that is ; with a running summary it is . For , even is operations — several seconds in C++ and minutes in Python. Sliding window gets the same answer in , about operations, by never evaluating a subarray from scratch: it reuses the summary of the previous window and adjusts it by one element at a time.

The technique has two roots. One is signal processing: the moving average of a time series, computed since at least the 1920s by adding the newest sample and subtracting the oldest, is a fixed-size window. The other is networking: TCP's sliding window flow control (RFC 793, 1981) describes a range of byte sequence numbers that the sender may transmit, which slides forward as acknowledgements arrive. The algorithmic pattern as taught today — a right pointer that grows the window and a left pointer that shrinks it under a predicate — is competitive-programming folklore from the 2000s, and it is a special case of the two-pointer technique in which both pointers move in the same direction and the object of interest is what lies between them.

In production you meet windows constantly. Rate limiters count requests in the last second. Monitoring systems compute p99 latency over the last five minutes. Stream processors (Flink, Kafka Streams, Spark Structured Streaming) expose tumbling, hopping and sliding windows as first-class operators. Network stacks compute congestion windows. Text search finds the shortest passage containing all query terms. All of these are the same loop: admit at the right, evict at the left, keep a summary current.

Pattern triggers

If the problem says or has…Think of…
"contiguous subarray", "substring" (never "subsequence")A window — subsequences are not contiguous and need DP or greedy instead
"of size k", "k consecutive", "every window of length k"Fixed-size window: one add, one remove per step
"longest … such that …" with a property that survives shrinking (at most distinct, no repeats, at most zeroes, sum )Variable window, grow then shrink-while-invalid, record the maximum
"shortest … such that …" with a property that survives growing (contains all of , sum with positive numbers)Variable window, grow then shrink-while-valid, record the minimum
"number of subarrays with at most …"Variable window; add right - left + 1 at every step
"number of subarrays with exactly …"atMost(k) - atMost(k-1)
"anagram", "permutation of", "same letters"Fixed window with a frequency array and a matches counter
"contains all characters of", "covers every word"Variable window with need/have counters
"all elements positive", "all elements at least 1"A strong hint that sum-based windows are monotone and the window technique applies
Negative numbers allowed plus a sum conditionWarning: the window predicate is not monotone — switch to prefix sums and a monotonic deque
"maximum / minimum of each window"A fixed window with a monotonic deque, not a counter — see Monotonic Stack & Deque
"last N seconds", "per minute", "in the last 24 hours"A time-based window over a stream; a deque of timestamps or a ring of buckets

One trigger deserves emphasis: monotonicity of the predicate. The variable window works only when the property being tested behaves consistently under growing and shrinking. "No repeated characters" survives shrinking (a sub-window of a repeat-free window is repeat-free) — so once a window becomes invalid, shrinking from the left is the only way to fix it, and growing can never fix it. "Sum at least " with positive numbers survives growing. If you cannot state which of these holds, the window may be the wrong tool; the Correctness section makes this precise.

Intuition & first principles

Think of the window as a bounded buffer with two gates. The right gate admits one element per step; the left gate evicts elements when the buffer is in a state you do not want. You never look inside the buffer by scanning it — you maintain a summary that can be updated in when one element enters or leaves. The summary is the entire design problem. For a sum it is one integer. For "no repeats" it is a set, or better a map from value to last-seen index. For "contains all of " it is a frequency table plus a single integer saying how many distinct requirements are currently satisfied.

Now the three flavours, as a decision tree.

flowchart TD
    Q["Contiguous subarray / substring question"] --> F{"Window size fixed by the problem?"}
    F -->|"yes: size k"| FX["Fixed window\nadd a[r], remove a[r-k]"]
    F -->|"no"| M{"Property survives shrinking\nor survives growing?"}
    M -->|"shrinking (at most k, no repeats)"| L["Grow right\nshrink left while invalid\nrecord longest"]
    M -->|"growing - sum at least s, covers t"| S["Grow right\nshrink left while valid\nrecord shortest"]
    M -->|"neither (negatives + sum)"| P["Not a window\nprefix sums + monotonic deque"]
    FX --> SUM{"What summary?"}
    L --> SUM
    S --> SUM
    SUM -->|"a number"| N["running sum / count"]
    SUM -->|"a set of values"| H["hash map of counts\n+ distinct counter"]
    SUM -->|"a multiset requirement"| NH["need / have counters"]

Fixed-size window. The window always has length . At step (for ) element a[r] enters and a[r-k] leaves. Two updates to the summary per step; no decisions. The first window is built by a loop of additions, after which there are slides, so the total work is summary updates. Notice that fixed windows do not require positivity or monotonicity of anything — the sum of every length- window is computed exactly, negatives included. Monotonicity only becomes a requirement when the window size is chosen by the algorithm.

Variable-size window for "longest". The right pointer advances one element per outer iteration. After admitting a[r], if the window has become invalid, evict from the left until it is valid again. Then the window [left, r] is the longest valid window ending at r, and the answer is the maximum of r - left + 1 over all r. The key fact — proved below — is that left never needs to move backward, so its total movement is at most and the inner while loop costs in total, not per step.

Variable-size window for "shortest". Same two pointers, opposite roles for the predicate: after admitting a[r], while the window satisfies the requirement, record its length and evict from the left. The loop stops at the first left for which the window no longer satisfies it, so [left - 1, r] was the shortest satisfying window ending at r.

Counting. For "number of subarrays with at most of something", observe that after the shrink step the window [left, r] is the longest valid window ending at r, and every sub-window [l', r] with is also valid (because validity survives shrinking). That is r - left + 1 valid subarrays ending at r. Summing over r counts every valid subarray exactly once, grouped by its right endpoint.

Why this is "two pointers". left and right are two indices into one array, both moving right, each moving at most times. The two-pointers page proves the pattern "the pointer I move cannot be part of a better answer"; here the pointer is left, and the claim is "no window starting before left and ending at or after right can be valid". The window is what lies between the pointers rather than the pair of endpoints.

Mechanics

Fixed-size window

Maximum sum of consecutive elements. Build s = a[0] + ... + a[k-1]. For r from k to n-1: s += a[r] - a[r-k], best = max(best, s). On [2, 1, 5, 1, 3, 2] with k = 3 the window sums are 8, 7, 9, 6 and the answer is 9 (verified by script). Averages are the same with a division at the end — keep the sum as an integer and divide once per window to avoid accumulating floating-point error; LeetCode 643's example [1, 12, -5, -6, 50, 3], k = 4 gives window sums 2, 51 and the maximum average .

Anagram detection with a 26-count array and a matches counter. To find every window of s that is an anagram of p (length ), keep diff[c] = count_window[c] - count_p[c] for each of the 26 letters, and matches = the number of letters with diff[c] == 0. The window is an anagram exactly when matches == 26. When a character c enters: diff[c] += 1; if it became 0, matches += 1; if it became 1, matches -= 1. When c leaves: diff[c] -= 1; if it became 0, matches += 1; if it became , matches -= 1. This makes the per-step check instead of comparing two 26-element arrays (). On s = "cbaebabacd", p = "abc" the anagram windows start at indices 0 and 6 (verified). The same technique solves "permutation in string" (s1 = "ab" is a permutation of some window of s2 = "eidbaooo": yes, the window "ba").

Variable-size window: the template

flowchart TD
    I["left = 0, best = 0, empty summary"] --> R{"right < n ?"}
    R -->|"no"| D["return best"]
    R -->|"yes"| ADD["admit a[right] into the summary"]
    ADD --> V{"window [left, right] invalid ?"}
    V -->|"yes"| EV["evict a[left] from the summary\nleft = left + 1"] --> V
    V -->|"no"| REC["best = max(best, right - left + 1)"]
    REC --> NX["right = right + 1"] --> R

In code shape (a fragment, not runnable):

# fragment — the longest-valid-window template
left = 0
for right in range(n):
    add(a[right])                    # summary now describes [left, right]
    while invalid():                 # cannot be fixed by growing; shrink
        remove(a[left])
        left += 1
    best = max(best, right - left + 1)   # [left, right] is the longest valid window ending at right

For "shortest", swap the roles: while valid(): best = min(best, right - left + 1); remove(a[left]); left += 1. Note where the answer is recorded: for "longest", after the shrink loop (the window is valid then); for "shortest", inside the shrink loop (the window is valid at the top of each iteration and may become invalid after the eviction).

The amortized accounting. Each element is admitted exactly once (right takes each value once) and evicted at most once (left only increases, and never exceeds right + 1). So the total number of add and remove calls is at most , and if each is the whole algorithm is regardless of how many times the inner while runs in any single outer iteration. A script that counts pointer moves on random arrays of length 10, 100 and 1000 reports 15, 198 and 1998 moves respectively — always , and approaching as windows churn. This is the same accounting argument as the amortized analysis of a dynamic array's push (Complexity Analysis): charge each element two coins at admission, one for entering and one for its eventual eviction.

Windows with hash-map counters

Longest substring without repeating characters. Summary: last[c] = index of the most recent occurrence of character c. When s[right] has a previous occurrence at or after left, the window [left, right] contains a repeat, and the only way to remove it is to move left past that occurrence: left = last[c] + 1. This is a jump rather than a step-by-step shrink — the map tells us exactly where left must go. The condition last[c] >= left is essential: an occurrence before left is already outside the window and must not drag left backward (the string "abba" is the classic test: at the final a, last['a'] = 0 < left = 2, so left stays and the answer is 2, not 3).

Trace on s = "abcabcbb" (computed by script; "last" is the previous index of the character before this step):

rightcharlast seenleft (after)windowlengthbest
0a—0a11
1b—0ab22
2c—0abc33
3a01bca33
4b12cab33
5c23abc33
6b45cb23
7b67b13

At right = 6 the previous b was at index 4, inside the window [3, 6], so left jumps from 3 to 5 — two positions in one step. The answer is 3 ("abc").

Longest with at most distinct. Summary: a map from value to count, and the number of keys with positive count. Admit a[right]; while the map has more than keys, evict a[left] (decrement; delete the key when it hits zero). Fruit into baskets is this with : on [1, 2, 3, 2, 2] the longest window with at most two distinct values is [3, 2, 2] plus... no — it is [2, 3, 2, 2] of length 4 (verified by script). The map's key count is what makes "number of distinct" an query.

Minimum window substring. Given s and t, find the shortest window of s containing every character of t with multiplicity. Summary: need[c] = count of c in t (fixed), window[c] = count of c in the current window, required = number of distinct characters in t, and have = number of distinct characters c with window[c] >= need[c]. The window is valid when have == required. On admitting c: increment window[c]; if it is now exactly need[c], increment have (it crossed from unsatisfied to satisfied; later increments do not change have). On evicting c: decrement window[c]; if it is now exactly need[c] - 1, decrement have. This have/required pair turns the "is every requirement met?" check from to .

Trace on s = "ADOBECODEBANC", t = "ABC" — every step, including each shrink (computed by script):

Stepleftrightactionhave / requiredwindowbest so far
expand00+A1 / 3A—
expand01+D1 / 3AD—
expand02+O1 / 3ADO—
expand03+B2 / 3ADOB—
expand04+E2 / 3ADOBE—
expand05+C3 / 3ADOBEC—
shrink15−A2 / 3DOBECADOBEC (6)
expand16+O2 / 3DOBECOADOBEC
expand17+D2 / 3DOBECODADOBEC
expand18+E2 / 3DOBECODEADOBEC
expand19+B2 / 3DOBECODEBADOBEC
expand110+A3 / 3DOBECODEBAADOBEC
shrink210−D3 / 3OBECODEBAADOBEC
shrink310−O3 / 3BECODEBAADOBEC
shrink410−B3 / 3ECODEBAADOBEC
shrink510−E3 / 3CODEBAADOBEC
shrink610−C2 / 3ODEBAADOBEC
expand611+N2 / 3ODEBANADOBEC
expand612+C3 / 3ODEBANCADOBEC
shrink712−O3 / 3DEBANCADOBEC
shrink812−D3 / 3EBANCADOBEC
shrink912−E3 / 3BANCEBANC (5)
shrink1012−B2 / 3ANCBANC (4)

Read the shrink rows carefully: evicting B at step "shrink 4 / 10" does not drop have, because the window still contains the B at index 9. Only when C leaves at left = 5 does have fall to 2 — there was exactly one C. The final answer is "BANC", length 4. Thirteen expansions and ten shrinks: 23 pointer moves for , within the bound.

Permutation in string / find all anagrams are fixed windows (the length is ), so they belong to the first family even though they use a frequency table. Use the matches counter described above.

"At most k" → "exactly k" by subtraction

Counting subarrays with exactly distinct values is not directly a window problem: the set of windows with exactly distinct values is not closed under shrinking (shrink and you may drop to ). But "at most " is closed under shrinking, so atMost(k) is a standard counting window, and

On [1, 2, 1, 2, 3] with : atMost(2) = 12, atMost(1) = 5, so exactly(2) = 7, and a brute-force enumeration confirms 7 (verified). The same subtraction counts subarrays with exactly odd numbers ("nice subarrays"): on [1, 1, 2, 1, 1], , the answer is 2. Two passes of each; still .

Shortest subarray with sum ≥ s — and why negatives break it

With positive numbers, "sum " survives growing: adding an element never decreases the sum. So the shortest-window template applies: admit a[right]; while sum >= s, record the length and evict from the left. On [2, 3, 1, 2, 4, 3] with the answer is 2 ([4, 3]), verified.

Now allow negatives. Take a = [1, -1, 3], . The template admits 1 (sum 1), admits (sum 0), admits 3 (sum 3 3): records length 3, evicts the 1 (sum 2, stop). It answers 3. The correct answer is 1: the subarray [3] alone has sum 3. What went wrong? After evicting the 1, the sum dropped below and the shrink stopped — but evicting the as well would have raised the sum back to 3. The predicate "sum " is not monotone under shrinking when negatives are present: a window can be invalid while a sub-window of it is valid. The template's stopping rule assumes that once shrinking makes the window invalid, all further shrinks are also invalid, and that assumption is false. LeetCode 862's example [84, -37, 32, 40, 95], fails the same way: the window gives 5, the truth is 3 (32 + 40 + 95 = 167).

The fix is a different algorithm. Compute prefix sums , ; a subarray [l, r) has sum , so for each r you want the largest with . A monotonic deque of candidate l values (indices with increasing prefix sums) answers that in amortized : pop from the front while (recording r - front), and pop from the back while (a later index with a smaller-or-equal prefix sum dominates an earlier one with a larger prefix). This is the subject of Prefix Sums and Monotonic Stack & Deque; the point here is to recognise the trigger — negatives plus a sum condition — and not to reach for the window.

Sliding window maximum (preview)

"Maximum of every window of size " is a fixed window whose summary is the maximum, and a maximum cannot be updated in when an element leaves (if the leaving element was the maximum, you must find the next one). The solution is a deque of indices with decreasing values: push right after popping every index whose value is (it can never be a future maximum while right is in the window), pop the front when it falls out of the window, and the front is always the current maximum. Amortized per step by the same two-coins argument. Full treatment in Monotonic Stack & Deque.

Windows over streams and time

When the data is a stream you cannot index a[r-k]; you keep the last elements in a ring buffer (Queues, Deques & Circular Buffers) and the element that leaves is the one the new element overwrites. A moving average over a stream is time and space per update.

Time-based windows replace "the last elements" with "the elements from the last seconds", so the window's element count varies. A sliding log rate limiter keeps a deque of request timestamps, evicts from the front while front < now - W, and admits a request if the deque's size is below the limit — exact, but memory per client. A sliding window counter approximates it with two fixed buckets: count in the current bucket plus the previous bucket's count weighted by the fraction of the previous bucket still inside the window. A fixed window counter resets every seconds and allows up to the limit at a boundary. The trade-offs are the subject of Rate Limiting and the hands-on Build a Rate Limiter.

flowchart LR
    REQ["request at t = now"] --> EVICT["pop front while front < now - W"]
    EVICT --> SZ{"size < limit ?"}
    SZ -->|"yes"| ADMIT["push now, allow"]
    SZ -->|"no"| DENY["reject (429)"]
    subgraph DQ["deque of timestamps inside the window"]
        T1["now - 0.9s"] --> T2["now - 0.6s"] --> T3["now - 0.1s"]
    end

TCP's sliding window is the namesake. The sender keeps a range of byte sequence numbers it is allowed to have in flight: from the oldest unacknowledged byte up to that plus the window size advertised by the receiver (and limited by the congestion window). As ACKs arrive, the left edge advances and the window slides, freeing the sender to transmit more. It is literally a window of [left, right] over the byte stream, with left moved by acknowledgements and right by the receiver's advertised capacity. Details in TCP/IP Deep Dive.

flowchart LR
    A["bytes acked\n(left of window)"] --> B["sent, awaiting ACK"] --> C["may send now\n(up to advertised window)"] --> D["cannot send yet"]
Right grows the window by one each step; left only moves forward to evict a repeat, so every character enters and leaves at most once — O(n) in total.

The ladder: brute force → better → optimal

Running example: longest substring without repeating characters.

Rung 1 — enumerate all substrings and check each, . For each pair (i, j), check that s[i..j] has no repeats by building a set (). There are substrings and each check is . For that is on the order of operations — infeasible. With a 26-letter alphabet the answer is at most 26, which bounds the useful j - i, but the general case (Unicode input) has no such bound.

Rung 2 — for each start, extend until a repeat, . Fix i; walk j rightward adding s[j] to a set; stop at the first repeat. The set is reused across j, so each i costs and the total is . The improvement comes from not rebuilding the set per substring. For this is about operations — acceptable in C++, slow in Python.

Rung 3 — one window with a last-seen map, . The observation that unlocks the last rung: when the window [left, right] becomes invalid because s[right] repeats an earlier s[p] with , every start position in [left, p] is also doomed for every end (they all contain both copies). So left can jump straight to p + 1. There is no reason to re-examine starts between the old left and p — rung 2 did, and that is where its extra factor of went. Each character is admitted once and left only increases: time, space for the map.

RungTimeSpaceKey idea
All substrings, check eachNone — the baseline
Fix start, extend to first repeatReuse the set while extending
One window, last-seen mapA repeat dooms every start up to it; jump left

The ladder for "shortest subarray with sum " (positive numbers) has the same shape: pairs with a running sum → by binary-searching prefix sums → window. And the ladder for fixed windows is one step: by recomputing each window → by add/remove.

Correctness

The condition: hereditary (monotone) predicates

Let be the predicate "window is valid". Call hereditary if validity is inherited by sub-windows:

Equivalently — the contrapositive, which is how it is usually stated — if is invalid then so is every window that contains it: for and for . "No repeated characters", "at most distinct", "at most zeroes", "sum with non-negative numbers" are all hereditary. "Sum with positive numbers" is hereditary for the complement: invalidity is inherited by sub-windows, which is what the shortest-window template needs. "Sum with arbitrary signs" is neither, and the counter-example above shows the template failing.

Theorem (longest-window template)

If is hereditary and add/remove keep the summary equal to the true summary of , then after the shrink loop at step right, is the longest valid window ending at right, and best is the length of the longest valid window overall.

Define = the smallest such that holds (assume holds for every , i.e. single elements are valid; if not, the template needs a guard, see Pitfalls).

Lemma: is non-decreasing. If holds then by heredity holds, so .

Invariant: at the end of iteration right, left = L(right).

Initialisation. Before the loop, left = 0 and the window is empty. At right = 0, after admitting a[0], the window is valid, the shrink loop does not run, and left = 0 = L(0).

Maintenance. Assume left = L(right - 1) at the start of iteration right. By the lemma, $L(\text{right}) \ge L(\text{right}-1) = $ left, so the correct new left is at or to the right of the current one — left never has to move backward, which is the fact that lets us only ever increment it. The shrink loop increments left while is false. By heredity, every has false (otherwise would be smaller), so the loop does not stop early; and it stops as soon as left because that window is valid. Hence left = L(right) after the loop.

Answer. right - L(right) + 1 is by definition the length of the longest valid window ending at right. Every window ends somewhere, so the maximum over right is the global optimum.

The shortest-window template has the mirror proof with "invalidity is hereditary": define = the largest with ; it is non-decreasing; the loop evicts while valid and stops at ; the shortest valid window ending at is , recorded just before the eviction that broke it.

Counting

For "number of valid subarrays" with hereditary : after the shrink at step right, the valid windows ending at right are exactly for — all of them by heredity, and none with smaller by the definition of . That is right - left + 1 windows, each counted once (at its right endpoint).

Where the negative-number case breaks the proof

The lemma used heredity to conclude . For "sum " with negatives, the set of valid for a fixed is not an interval: in [1, -1, 3] with and , is valid (sum 3), is invalid (sum 2), is valid (sum 3). The shrink loop stops at the first invalid and never sees the valid . No change to the loop condition fixes this; the information needed ("is there any later that works?") is not in a single running sum. That is why the correct algorithm maintains a set of candidate starts (the monotonic deque over prefix sums).

Complexity

Fixed window. Exactly admissions and evictions: time for any input, extra space for a numeric summary, for a frequency table (26 ints for lowercase letters, 128 or 256 for ASCII/bytes, a hash map for Unicode). Best, average and worst case are the same.

Variable window. At most admissions and evictions by the two-coins argument: summary operations. With an summary (sum, count, array-indexed frequency table), time worst case. With a hash-map summary, expected time (Hash Tables — adversarial inputs can degrade a hash map; use arrays when the alphabet is small). Space for the map — at most one entry per distinct value in the window. The "exactly " trick doubles the constant, still .

Why the inner while does not make it . A single outer iteration may run the inner loop times (if the whole window must be evicted). But the sum of inner iterations over the whole run is bounded by the total distance left travels, which is at most . Amortized per outer step, total. Students who have not internalised this look at the nested loops and say ; interviewers notice.

Constants and cache. A window loop reads the array sequentially (two forward streams, right and left), so hardware prefetching makes it memory-bandwidth bound — roughly a few nanoseconds per element in a compiled language for a numeric summary. A hash-map summary is a different story: each add/remove is a hash computation and a probe, often 20–50 ns and a potential cache miss when the map is large. Replacing a HashMap<Character, Integer> with an int[128] is routinely a – speed-up for ASCII input; on LeetCode it is the difference between the 20th and the 99th percentile.

Implementation

Three canonical routines: fixed-window maximum sum, longest substring without repeating characters (variable window with a last-seen map), and minimum window substring (variable window with need/have counters). Each block is self-checking with identical test data.

from collections import Counter


def max_sum_window(nums: list[int], k: int) -> int:
    """Maximum sum over all windows of exactly k consecutive elements. Works with negatives."""
    if k <= 0 or k > len(nums):
        raise ValueError("k must be in 1..len(nums)")
    s = sum(nums[:k])
    best = s
    for r in range(k, len(nums)):
        s += nums[r] - nums[r - k]          # admit nums[r], evict nums[r-k]
        best = max(best, s)
    return best


def longest_unique_substring(s: str) -> int:
    """Length of the longest substring with no repeated character.
    Invariant after each step: s[left:right+1] has no repeats and is the longest such ending at right."""
    last: dict[str, int] = {}
    left = 0
    best = 0
    for right, ch in enumerate(s):
        prev = last.get(ch)
        if prev is not None and prev >= left:    # repeat inside the window: jump left past it
            left = prev + 1
        last[ch] = right
        best = max(best, right - left + 1)
    return best


def min_window(s: str, t: str) -> str:
    """Shortest substring of s containing every character of t with multiplicity, or ''."""
    if not t or len(t) > len(s):
        return ""
    need = Counter(t)
    required = len(need)                 # distinct characters that must be satisfied
    window: dict[str, int] = {}
    have = 0                             # distinct characters currently satisfied
    left = 0
    best_len, best_left = len(s) + 1, 0
    for right, ch in enumerate(s):
        window[ch] = window.get(ch, 0) + 1
        if ch in need and window[ch] == need[ch]:
            have += 1                    # crossed from unsatisfied to satisfied
        while have == required:          # valid: record, then try to shrink
            if right - left + 1 < best_len:
                best_len, best_left = right - left + 1, left
            lc = s[left]
            window[lc] -= 1
            if lc in need and window[lc] < need[lc]:
                have -= 1                # crossed back to unsatisfied
            left += 1
    return "" if best_len > len(s) else s[best_left:best_left + best_len]


if __name__ == "__main__":
    assert max_sum_window([2, 1, 5, 1, 3, 2], 3) == 9
    assert max_sum_window([1, -1, 5, -2, 3, -3], 2) == 4
    assert max_sum_window([5], 1) == 5

    assert longest_unique_substring("abcabcbb") == 3
    assert longest_unique_substring("bbbbb") == 1
    assert longest_unique_substring("pwwkew") == 3
    assert longest_unique_substring("") == 0
    assert longest_unique_substring("abba") == 2

    assert min_window("ADOBECODEBANC", "ABC") == "BANC"
    assert min_window("a", "a") == "a"
    assert min_window("a", "aa") == ""
    assert min_window("aa", "aa") == "aa"
    assert min_window("ab", "b") == "b"
    print("all tests passed")
import java.util.HashMap;
import java.util.Map;

public class SlidingWindow {

    /** Maximum sum over all windows of exactly k consecutive elements. Works with negatives. */
    static long maxSumWindow(int[] nums, int k) {
        if (k <= 0 || k > nums.length) throw new IllegalArgumentException("k must be in 1..nums.length");
        long sum = 0;
        for (int i = 0; i < k; i++) sum += nums[i];
        long best = sum;
        for (int r = k; r < nums.length; r++) {
            sum += nums[r] - nums[r - k];          // admit nums[r], evict nums[r-k]
            best = Math.max(best, sum);
        }
        return best;
    }

    /** Length of the longest substring with no repeated character (UTF-16 code units). */
    static int longestUniqueSubstring(String s) {
        Map<Character, Integer> last = new HashMap<>();
        int left = 0, best = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            Integer prev = last.get(c);
            if (prev != null && prev >= left) left = prev + 1;   // jump past the repeat
            last.put(c, right);
            best = Math.max(best, right - left + 1);
        }
        return best;
    }

    /** Shortest substring of s containing every character of t with multiplicity, or "". */
    static String minWindow(String s, String t) {
        if (t.isEmpty() || t.length() > s.length()) return "";
        Map<Character, Integer> need = new HashMap<>();
        for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);
        Map<Character, Integer> window = new HashMap<>();
        int required = need.size(), have = 0, left = 0;
        int bestLen = Integer.MAX_VALUE, bestLeft = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            int cnt = window.merge(c, 1, Integer::sum);
            if (need.containsKey(c) && cnt == need.get(c)) have++;
            while (have == required) {
                if (right - left + 1 < bestLen) { bestLen = right - left + 1; bestLeft = left; }
                char lc = s.charAt(left);
                int lcnt = window.merge(lc, -1, Integer::sum);
                if (need.containsKey(lc) && lcnt < need.get(lc)) have--;
                left++;
            }
        }
        return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestLeft, bestLeft + bestLen);
    }

    static void check(boolean ok, String what) {
        if (!ok) throw new AssertionError("FAILED: " + what);
    }

    public static void main(String[] args) {
        check(maxSumWindow(new int[]{2, 1, 5, 1, 3, 2}, 3) == 9, "max sum window");
        check(maxSumWindow(new int[]{1, -1, 5, -2, 3, -3}, 2) == 4, "max sum window negatives");
        check(maxSumWindow(new int[]{5}, 1) == 5, "max sum window single");

        check(longestUniqueSubstring("abcabcbb") == 3, "unique abcabcbb");
        check(longestUniqueSubstring("bbbbb") == 1, "unique bbbbb");
        check(longestUniqueSubstring("pwwkew") == 3, "unique pwwkew");
        check(longestUniqueSubstring("") == 0, "unique empty");
        check(longestUniqueSubstring("abba") == 2, "unique abba");

        check(minWindow("ADOBECODEBANC", "ABC").equals("BANC"), "min window BANC");
        check(minWindow("a", "a").equals("a"), "min window a");
        check(minWindow("a", "aa").isEmpty(), "min window impossible");
        check(minWindow("aa", "aa").equals("aa"), "min window aa");
        check(minWindow("ab", "b").equals("b"), "min window b");
        System.out.println("all tests passed");
    }
}
#include <algorithm>
#include <array>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>

// Maximum sum over all windows of exactly k consecutive elements. Works with negatives.
long long maxSumWindow(const std::vector<int>& nums, int k) {
    if (k <= 0 || k > static_cast<int>(nums.size())) throw std::invalid_argument("k must be in 1..n");
    long long sum = 0;
    for (int i = 0; i < k; ++i) sum += nums[i];
    long long best = sum;
    for (int r = k; r < static_cast<int>(nums.size()); ++r) {
        sum += nums[r] - nums[r - k];          // admit nums[r], evict nums[r-k]
        best = std::max(best, sum);
    }
    return best;
}

// Length of the longest substring with no repeated byte. Array-indexed: O(1) per step.
int longestUniqueSubstring(const std::string& s) {
    std::array<int, 256> last;
    last.fill(-1);
    int left = 0, best = 0;
    for (int right = 0; right < static_cast<int>(s.size()); ++right) {
        unsigned char c = static_cast<unsigned char>(s[right]);
        if (last[c] >= left) left = last[c] + 1;   // jump past the repeat
        last[c] = right;
        best = std::max(best, right - left + 1);
    }
    return best;
}

// Shortest substring of s containing every byte of t with multiplicity, or "".
std::string minWindow(const std::string& s, const std::string& t) {
    if (t.empty() || t.size() > s.size()) return "";
    std::array<int, 256> need{};
    std::array<int, 256> window{};
    int required = 0;
    for (unsigned char c : t) if (need[c]++ == 0) ++required;
    int have = 0, left = 0, bestLen = INT_MAX, bestLeft = 0;
    for (int right = 0; right < static_cast<int>(s.size()); ++right) {
        unsigned char c = static_cast<unsigned char>(s[right]);
        if (++window[c] == need[c]) ++have;          // need[c] == 0 can never match: window[c] >= 1
        while (have == required) {
            if (right - left + 1 < bestLen) { bestLen = right - left + 1; bestLeft = left; }
            unsigned char lc = static_cast<unsigned char>(s[left]);
            if (--window[lc] < need[lc]) --have;     // for lc not in t, need == 0 and window >= 0
            ++left;
        }
    }
    return bestLen == INT_MAX ? "" : s.substr(bestLeft, bestLen);
}

static void check(bool ok, const char* what) {
    if (!ok) { std::cerr << "FAILED: " << what << "\n"; std::exit(1); }
}

int main() {
    check(maxSumWindow({2, 1, 5, 1, 3, 2}, 3) == 9, "max sum window");
    check(maxSumWindow({1, -1, 5, -2, 3, -3}, 2) == 4, "max sum window negatives");
    check(maxSumWindow({5}, 1) == 5, "max sum window single");

    check(longestUniqueSubstring("abcabcbb") == 3, "unique abcabcbb");
    check(longestUniqueSubstring("bbbbb") == 1, "unique bbbbb");
    check(longestUniqueSubstring("pwwkew") == 3, "unique pwwkew");
    check(longestUniqueSubstring("") == 0, "unique empty");
    check(longestUniqueSubstring("abba") == 2, "unique abba");

    check(minWindow("ADOBECODEBANC", "ABC") == "BANC", "min window BANC");
    check(minWindow("a", "a") == "a", "min window a");
    check(minWindow("a", "aa").empty(), "min window impossible");
    check(minWindow("aa", "aa") == "aa", "min window aa");
    check(minWindow("ab", "b") == "b", "min window b");
    std::cout << "all tests passed\n";
    return 0;
}
import assert from "node:assert/strict";

/** Maximum sum over all windows of exactly k consecutive elements. Works with negatives. */
function maxSumWindow(nums: number[], k: number): number {
  if (k <= 0 || k > nums.length) throw new RangeError("k must be in 1..nums.length");
  let sum = 0;
  for (let i = 0; i < k; i++) sum += nums[i];
  let best = sum;
  for (let r = k; r < nums.length; r++) {
    sum += nums[r] - nums[r - k];          // admit nums[r], evict nums[r-k]
    best = Math.max(best, sum);
  }
  return best;
}

/** Length of the longest substring with no repeated character (UTF-16 code units). */
function longestUniqueSubstring(s: string): number {
  const last = new Map<string, number>();
  let left = 0;
  let best = 0;
  for (let right = 0; right < s.length; right++) {
    const c = s[right];
    const prev = last.get(c);
    if (prev !== undefined && prev >= left) left = prev + 1;   // jump past the repeat
    last.set(c, right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

/** Shortest substring of s containing every character of t with multiplicity, or "". */
function minWindow(s: string, t: string): string {
  if (t.length === 0 || t.length > s.length) return "";
  const need = new Map<string, number>();
  for (const c of t) need.set(c, (need.get(c) ?? 0) + 1);
  const window = new Map<string, number>();
  const required = need.size;
  let have = 0;
  let left = 0;
  let bestLen = Infinity;
  let bestLeft = 0;
  for (let right = 0; right < s.length; right++) {
    const c = s[right];
    const cnt = (window.get(c) ?? 0) + 1;
    window.set(c, cnt);
    if (need.has(c) && cnt === need.get(c)) have++;
    while (have === required) {
      if (right - left + 1 < bestLen) {
        bestLen = right - left + 1;
        bestLeft = left;
      }
      const lc = s[left];
      const lcnt = (window.get(lc) ?? 0) - 1;
      window.set(lc, lcnt);
      if (need.has(lc) && lcnt < (need.get(lc) as number)) have--;
      left++;
    }
  }
  return bestLen === Infinity ? "" : s.slice(bestLeft, bestLeft + bestLen);
}

assert.equal(maxSumWindow([2, 1, 5, 1, 3, 2], 3), 9);
assert.equal(maxSumWindow([1, -1, 5, -2, 3, -3], 2), 4);
assert.equal(maxSumWindow([5], 1), 5);

assert.equal(longestUniqueSubstring("abcabcbb"), 3);
assert.equal(longestUniqueSubstring("bbbbb"), 1);
assert.equal(longestUniqueSubstring("pwwkew"), 3);
assert.equal(longestUniqueSubstring(""), 0);
assert.equal(longestUniqueSubstring("abba"), 2);

assert.equal(minWindow("ADOBECODEBANC", "ABC"), "BANC");
assert.equal(minWindow("a", "a"), "a");
assert.equal(minWindow("a", "aa"), "");
assert.equal(minWindow("aa", "aa"), "aa");
assert.equal(minWindow("ab", "b"), "b");
console.log("all tests passed");

Notes on the implementations. The C++ version indexes std::array<int, 256> by unsigned char: casting is mandatory, because a plain char may be signed and a byte would index negatively. Java's and TypeScript's versions iterate UTF-16 code units, so a character outside the Basic Multilingual Plane counts as two "characters" — correct for the ASCII inputs these problems use, wrong for emoji; iterate code points if that matters (see Pitfalls). In the Java minWindow, window.merge(c, 1, Integer::sum) returns the new count, which is what lets the have update stay one line. The fixed-window routines accumulate in 64-bit (long, long long) because values of magnitude up to overflow a 32-bit int at .

Variant: the "at most k" counting template

# fragment — count subarrays with at most k distinct; exactly k = at_most(k) - at_most(k-1)
def at_most_k_distinct(a, k):
    count = {}
    left = total = 0
    for right, x in enumerate(a):
        count[x] = count.get(x, 0) + 1
        while len(count) > k:                 # hereditary predicate: shrink until valid
            count[a[left]] -= 1
            if count[a[left]] == 0:
                del count[a[left]]
            left += 1
        total += right - left + 1             # every [l, right] with l >= left is valid
    return total

Real-world uses

Rate limiting. Every API gateway counts requests per client per window. The sliding log (deque of timestamps) is the exact algorithm; the sliding window counter is the approximation that fits in two integers per client and is a common production choice (Cloudflare's 2017 engineering blog describes this approach for its rate limiter) because memory per client is the binding constraint at scale. Redis-based limiters implement the sliding log as a sorted set keyed by timestamp with ZREMRANGEBYSCORE for eviction. See Rate Limiting, Build a Rate Limiter and Redis Internals.

TCP flow and congestion control. The sender's usable window is minus bytes in flight; both edges move as ACKs arrive and as the congestion controller adjusts cwnd. The receiver's advertised window is a sliding window over its buffer. The whole of TCP's throughput behaviour (bandwidth-delay product, window scaling) follows from the window size and the round-trip time. See TCP/IP Deep Dive.

Stream processing. Flink, Kafka Streams and Spark Structured Streaming expose tumbling windows (fixed, non-overlapping), hopping/sliding windows (fixed size, fixed slide) and session windows (variable, closed by inactivity). Internally an aggregation over a hopping window is exactly the add/remove loop, with the complication that events arrive out of order and the window must wait for a watermark before closing.

Monitoring and SLOs. "Error rate over the last 5 minutes" and "p99 latency over the last hour" are sliding windows over metric streams. Exact percentiles over a window need a data structure that supports insert, delete and quantile — a sorted multiset or a sketch (Probabilistic Data Structures) — while sums and counts need only a ring of buckets.

Text and search. "Snippet generation" in a search engine — show the shortest passage of the document containing all query terms — is minimum window substring over tokens. Readability and plagiarism tools compute statistics over windows of words. Rolling hashes for substring search (Rabin–Karp, String Algorithms) are a fixed window whose summary is a hash updated by removing the leading character's contribution and adding the trailing one.

Signal processing and finance. Moving averages, exponentially weighted moving averages (which replace the exact window with a decaying weight so no eviction is needed), Bollinger bands (a moving mean and moving standard deviation — both maintainable incrementally with running sums of and ).

Compression. LZ77 and its descendants (DEFLATE in gzip/zlib/PNG, LZ4, Zstandard) search for repeated byte sequences inside a sliding window of recent output — typically 32 KB for DEFLATE — which is why the format is called "sliding window compression". The window bounds memory and the distance field of a back-reference.

Pitfalls & edge cases

Shrinking on the wrong condition. For "longest", the loop is while invalid; for "shortest", while valid. Mixing them up gives a loop that either never shrinks (answers are too long) or shrinks too eagerly. Decide which template you are in before writing the condition.

Recording the answer at the wrong moment. In the longest template the answer is recorded after the shrink loop, when the window is valid. In the shortest template it is recorded inside the loop, before each eviction, because the eviction may break validity. Recording a longest-window answer before shrinking counts invalid windows; recording a shortest-window answer after the loop records an invalid window.

Negative numbers with a sum predicate. The counter-example [1, -1, 3], above. Any time a problem allows negatives (or zeroes, for a strict-inequality predicate) and the window summary is a sum, stop and check monotonicity. Fixed-size windows are fine; variable-size windows over sums need prefix sums plus a monotonic deque, or a hash map of prefix sums for "exactly equal to" targets (Prefix Sums).

Counting "exactly k" directly. Trying to count windows with exactly distinct values in one window pass with a single left pointer is wrong (the valid starts for a given right form an interval, but its left edge is not left). Use atMost(k) - atMost(k-1), or the three-pointer variant that maintains both left_k (smallest start with at most distinct) and left_{k-1} and adds their difference.

Window length off by one. The window [left, right] inclusive has length right - left + 1. Writing right - left is the most common bug in this pattern; it also silently mis-handles the single-element window (length 0 instead of 1). If you prefer half-open windows [left, right) the length is right - left — pick one convention and keep it.

Forgetting to delete zero-count keys. When "number of distinct values" is len(counts), a key whose count has dropped to 0 must be removed from the map, or it still counts as distinct. In C++/Java with an array, track the number of non-zero entries explicitly instead.

have updates on the wrong comparison. In minimum window substring, increment have only when window[c] becomes equal to need[c] (not >=, which would increment repeatedly), and decrement only when it drops to exactly need[c] - 1 (not <, applied before the decrement). Off-by-one here makes have drift and the window either never valid or always valid.

Characters not in t. They must still be admitted and evicted (they are part of the window) but must not affect have. Guard with if c in need (Python/Java/TS) or rely on need[c] == 0 never matching a positive count (C++ arrays).

Unicode in JavaScript and Java. s[i], s.charAt(i) and s.length work in UTF-16 code units. "😀".length === 2. A window over code units can split a surrogate pair, and a frequency map keyed by code unit will treat the two halves as separate "characters". Use Array.from(s) / s.codePoints() to get code points, and expect the count array approach to become a map. Python 3 strings are sequences of code points, so s[i] is a character — but grapheme clusters (a base letter plus combining marks) are still multiple code points. See Strings in Depth.

k larger than n, or zero. A fixed window with has no windows; decide whether that is an error or an empty answer and handle it before the first loop, which would otherwise index out of range.

Single elements that are invalid. The longest-window proof assumed V(r, r) holds. If a single element can be invalid (e.g. "sum " with an element larger than ), the shrink loop runs until left = right + 1 and the window is empty; right - left + 1 = 0, which is a correct length for "no valid window ending here", but the summary code must tolerate the empty window (no negative counts, no division by zero for averages).

Variations

Two windows / "at most minus at most ". Covered above. The three-pointer variant runs both left pointers in one pass and is sometimes asked as a follow-up: at each right, the number of windows with exactly distinct ending at right is left_{k-1} - left_k where each left is the smallest start with at most that many distinct values.

Circular arrays by doubling. A window that may wrap around the end of a circular array of length becomes an ordinary window over the array concatenated with itself (indices modulo , right up to ), with the extra constraint right - left + 1 <= n. Each wrapped window appears exactly once as a contiguous window of the doubled array. Problems: maximum sum circular subarray, "minimum swaps to group all 1s together" on a circular binary array.

Windows on linked lists. A fixed window over a singly linked list is two cursors apart — admit at the leading cursor, evict at the trailing one. Random access is not needed because both cursors only move forward. See Linked Lists.

2D windows via prefix sums. The sum of every sub-grid cannot be slid in by adding one element and removing one — a step changes cells. Use a 2D prefix-sum table so any rectangle sum is four lookups, then iterate the positions. For "maximum of every window", apply the 1D monotonic-deque algorithm along rows, then along columns of the result. See Prefix Sums and Matrices & 2D Grids.

Windows with a monotonic deque — maximum/minimum per window, shortest subarray with sum with negatives: Monotonic Stack & Deque.

Windows with a balanced structure. When the summary is a median or an arbitrary quantile, the window needs insert/delete/k-th: two heaps with lazy deletion, an order-statistics tree, or a Fenwick tree over values (Advanced Data Structures). per step.

Exponentially weighted windows. Replace "evict after " with "multiply the summary by then add the new element". No eviction, memory, but the window has no sharp edge. Used by TCP's RTT estimator and by load averages in uptime.

Word-level windows. "Substring with concatenation of all words" slides a window of whole words of fixed width ; run the variable-window template once per starting offset so that windows are aligned to word boundaries.

Practice ladder

Easy → hard. Descriptions are paraphrased; follow the links for exact statements and constraints.

1. Maximum Average Subarray I (LeetCode 643) — the largest average over all windows of length exactly . Teaches the fixed window with a running sum; divide once at the end.

Hint

Keep the sum as an integer; best_sum over windows; return best_sum / k.

2. Longest Substring Without Repeating Characters (LeetCode 3) — the page's running example. Teaches the last-seen map and the prev >= left guard. Its CSES twin is Playlist (CSES 1141), with integers instead of characters and .

Hint

left = max(left, last[c] + 1) — never let left move backward.

3. Permutation in String (LeetCode 567) — does s2 contain any permutation of s1 as a substring? Teaches the fixed window with a 26-count array and the matches counter.

Hint

Window length ; maintain diff[c] and matches; answer is whether matches == 26 ever holds.

4. Find All Anagrams in a String (LeetCode 438) — all start indices of anagrams of p in s. Same machinery as 567, collecting every hit.

Hint

Same as 567 but push left whenever matches == 26 after the window reaches full size.

Solution
def find_anagrams(s: str, p: str) -> list[int]:
    k = len(p)
    if k > len(s):
        return []
    diff = [0] * 26                      # window count minus p count, per letter
    for ch in p:
        diff[ord(ch) - 97] -= 1
    matches = sum(1 for d in diff if d == 0)

    def shift(idx: int, delta: int) -> None:
        nonlocal matches
        before = diff[idx]
        diff[idx] += delta
        if before == 0:
            matches -= 1                 # was balanced, no longer
        elif diff[idx] == 0:
            matches += 1                 # became balanced

    out: list[int] = []
    for right, ch in enumerate(s):
        shift(ord(ch) - 97, +1)
        if right >= k:
            shift(ord(s[right - k]) - 97, -1)
        if right >= k - 1 and matches == 26:
            out.append(right - k + 1)
    return out


assert find_anagrams("cbaebabacd", "abc") == [0, 6]
assert find_anagrams("abab", "ab") == [0, 1, 2]
assert find_anagrams("a", "ab") == []
assert find_anagrams("aaaa", "a") == [0, 1, 2, 3]
print("ok")

time, space. The shift helper updates matches in ; the alternative — comparing two 26-arrays per step — is , fine for LeetCode but the counter version is what you write when the alphabet is Unicode.

5. Minimum Size Subarray Sum (LeetCode 209) — shortest contiguous subarray of positive integers with sum at least target. Teaches the shortest-window template and the positivity precondition.

Hint

Admit; while sum >= target: record, evict. Ask yourself what breaks if a 0 or a negative appears.

Solution
def min_subarray_len(target: int, nums: list[int]) -> int:
    left = 0
    s = 0
    best = len(nums) + 1
    for right, x in enumerate(nums):
        s += x
        while s >= target:                       # valid: record, then shrink
            best = min(best, right - left + 1)
            s -= nums[left]
            left += 1
    return 0 if best > len(nums) else best


def brute(target: int, nums: list[int]) -> int:
    n = len(nums)
    best = n + 1
    for i in range(n):
        s = 0
        for j in range(i, n):
            s += nums[j]
            if s >= target:
                best = min(best, j - i + 1)
                break
    return 0 if best > n else best


assert min_subarray_len(7, [2, 3, 1, 2, 4, 3]) == 2
assert min_subarray_len(4, [1, 4, 4]) == 1
assert min_subarray_len(11, [1, 1, 1, 1, 1, 1, 1, 1]) == 0
import random
random.seed(3)
for _ in range(500):
    arr = [random.randint(1, 9) for _ in range(random.randint(1, 15))]
    t = random.randint(1, 40)
    assert min_subarray_len(t, arr) == brute(t, arr), (t, arr)
print("ok")

time, space. The randomized comparison against brute force uses only positive values — by design; with negatives, the two would disagree, which is a good experiment to run.

6. Subarray Sums I (CSES 1660) — count subarrays of positive integers with sum exactly , . Teaches that with positive numbers "exactly " also works with a window: for each right, shrink while sum > x, then check sum == x.

Hint

Since all values are positive, for each right there is at most one left with sum exactly , and the sum is monotone in left. Shrink while sum > x; count if sum == x. (Subarray Sums II allows negatives and needs a prefix-sum hash map.)

7. Fruit Into Baskets (LeetCode 904) — longest subarray with at most two distinct values. Teaches the count map and key deletion.

Hint

while len(count) > 2: evict. Delete keys that reach 0.

8. Max Consecutive Ones III (LeetCode 1004) — longest subarray of 1s after flipping at most zeroes. Teaches that "at most zeroes in the window" is the hereditary predicate; you never actually flip anything.

Hint

Count zeroes in the window; while zeros > k: evict. On [1,1,1,0,0,0,1,1,1,1,0], the answer is 6.

9. Longest Repeating Character Replacement (LeetCode 424) — longest substring that becomes a single repeated letter after at most replacements. Teaches the predicate length - max_frequency <= k and a subtle optimisation: the window never needs to shrink by more than one.

Hint

Valid iff (right - left + 1) - max(count) <= k. The maximum count only matters when it grows; a stale max_freq can only make the window not grow, never produce a wrong answer, so you can keep a historical maximum and never recompute.

Solution
def character_replacement(s: str, k: int) -> int:
    count = [0] * 26
    left = 0
    max_freq = 0                 # historical max over all windows seen; never decreases
    best = 0
    for right, ch in enumerate(s):
        idx = ord(ch) - 65
        count[idx] += 1
        max_freq = max(max_freq, count[idx])
        if (right - left + 1) - max_freq > k:     # invalid: shrink by exactly one
            count[ord(s[left]) - 65] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best


assert character_replacement("ABAB", 2) == 4
assert character_replacement("AABABBA", 1) == 4
assert character_replacement("AAAA", 0) == 4
assert character_replacement("ABCDE", 1) == 2
print("ok")

time, space. Why if rather than while, and why a stale max_freq is safe: the window length only ever grows or stays the same (one admit, at most one evict per step). The answer is the largest window that was ever valid. A window of length is valid iff some letter appears times in it; once we have seen a valid window of length , we only care whether a longer window becomes valid, which requires a larger count — so a historical max_freq that is too high for the current window can only prevent a shrink that would not have improved the answer anyway. This is a known subtle point; if an interviewer is unconvinced, write the straightforward while loop with a recomputed max — and obviously correct.

10. Count Number of Nice Subarrays (LeetCode 1248) — number of subarrays with exactly odd numbers. Teaches atMost(k) - atMost(k-1).

Hint

Odd count is a hereditary "at most" predicate. Two passes.

Solution
def number_of_subarrays(nums: list[int], k: int) -> int:
    def at_most(m: int) -> int:
        left = odd = total = 0
        for right, x in enumerate(nums):
            odd += x & 1
            while odd > m:
                odd -= nums[left] & 1
                left += 1
            total += right - left + 1
        return total
    return at_most(k) - at_most(k - 1)


def brute(nums: list[int], k: int) -> int:
    n = len(nums)
    return sum(1 for i in range(n) for j in range(i, n) if sum(x & 1 for x in nums[i:j + 1]) == k)


assert number_of_subarrays([1, 1, 2, 1, 1], 3) == 2
assert number_of_subarrays([2, 4, 6], 1) == 0
assert number_of_subarrays([2, 2, 2, 1, 2, 2, 1, 2, 2, 2], 2) == 16
import random
random.seed(11)
for _ in range(300):
    arr = [random.randint(1, 6) for _ in range(random.randint(1, 12))]
    kk = random.randint(1, 4)
    assert number_of_subarrays(arr, kk) == brute(arr, kk), (arr, kk)
print("ok")

time, space. The single-pass alternative counts, for each right, the number of even elements immediately to the left of the window's first odd element — equivalent, slightly faster, harder to get right.

11. Subarrays with K Different Integers (LeetCode 992) — number of subarrays with exactly distinct values. Same subtraction with a count map; teaches the map-deletion detail inside a counting window.

Hint

at_most_k_distinct from the fragment above, twice. On [1,2,1,2,3], : .

12. Minimum Window Substring (LeetCode 76) — the page's second trace. Teaches need/have.

Hint

Follow the trace table; the have update fires only on crossing need[c] exactly.

13. Minimum Operations to Reduce X to Zero (LeetCode 1658) — remove elements from either end to sum exactly to , minimising removals. Teaches the reframing: the kept middle is a contiguous subarray with sum total - x; find the longest such, with positive numbers.

Hint

Positive numbers ⇒ for each right, shrink while sum > total - x; if sum == total - x, candidate length. Answer is n - longest, or .

Solution
def min_operations(nums: list[int], x: int) -> int:
    goal = sum(nums) - x                 # sum the kept middle must have
    if goal < 0:
        return -1
    left = s = 0
    longest = -1
    for right, v in enumerate(nums):
        s += v
        while s > goal and left <= right:        # positives: sum is monotone in left
            s -= nums[left]
            left += 1
        if s == goal:
            longest = max(longest, right - left + 1)
    return -1 if longest < 0 else len(nums) - longest


assert min_operations([1, 1, 4, 2, 3], 5) == 2
assert min_operations([5, 6, 7, 8, 9], 4) == -1
assert min_operations([3, 2, 20, 1, 1, 3], 10) == 5
assert min_operations([1, 1], 2) == 2          # goal = 0: the empty middle, remove everything
print("ok")

time, space. The goal == 0 case is handled because an empty window (left == right + 1) has s == 0 and length 0, giving n - 0 = n removals.

14. Sliding Window Maximum (LeetCode 239) — the maximum of each window of size . A preview of the monotonic deque; try it with a plain window first to feel why a counter does not suffice.

Hint

Deque of indices with decreasing values; pop back while a[back] <= a[right]; pop front when it leaves the window; front is the answer. Full treatment in Monotonic Stack & Deque.

15. Substring with Concatenation of All Words (LeetCode 30) — all start indices where s contains a concatenation of every word in words (all the same length ) in some order. Teaches word-level windows: one pass per offset in , counters keyed by word.

Hint

For each offset, treat s as a sequence of words of length and run minimum-window-style need/have counting with a fixed window of len(words) words; when a word is not in need, reset the window. On "barfoothefoobarman", ["foo","bar"] the answer is [0, 9].

Common mistakes & interview follow-ups

"What if the numbers can be negative?" For fixed windows: nothing changes. For variable windows with a sum predicate: the window is wrong; show the [1, -1, 3] counter-example and switch to prefix sums with a monotonic deque (shortest/longest with sum ) or a hash map of prefix sums (count with sum exactly ). Interviewers ask this specifically to see whether you know the precondition or merely the template.

"What if the input is a stream?" Fixed windows need a ring buffer of the last elements ( memory) — or, for sums, just the last values; for time-based windows a deque of timestamps or a ring of time buckets. Variable windows need the whole window buffered, which may be unbounded; ask about the maximum window size. Minimum window substring over a stream is possible because left only moves forward — buffer from left onward.

"What if it is 2D?" Sums of sub-rectangles: 2D prefix sums, per query after preprocessing. Max of every : 1D monotonic deque along rows then along columns. Fixed-width windows that must be contiguous in 2D (e.g. "largest square of 1s") are usually DP, not windows.

"Can you do it in one pass instead of two for exactly k?" Yes — the three-pointer variant with left_k and left_{k-1}; be prepared to explain why the difference of the two left pointers is the count of windows with exactly distinct values ending at right.

"Why is this when there is a nested loop?" Give the two-coins argument: every element is admitted once and evicted at most once, so all inner-loop iterations across the whole run total at most .

"What if the alphabet is huge (Unicode)?" Frequency arrays become hash maps; expected per operation, worst-case worse; memory proportional to distinct characters in the window. The matches counter still works — it counts satisfied keys of the need map rather than 26 letters.

"Can you return the window itself, not just its length?" Record best_left along with best_len whenever the answer improves; slice once at the end. Do not build substrings inside the loop — that is per slice and silently makes the algorithm .

"The window is the whole array — does your code handle it?" For "longest", yes if the answer is recorded after the shrink at every step. For "shortest", the whole array is a valid answer only if nothing shorter exists; make sure the sentinel best = n + 1 (or Infinity) is distinguishable from "no answer".

Quick quiz

1. State the property a predicate must have for the "shrink while invalid, record longest" template to be correct, and give one predicate that has it and one that does not.

Answer

Hereditary (closed under taking sub-windows): if is valid then every with is valid. "At most distinct values" has it. "Sum with negative numbers allowed" does not — [1, -1, 3] with is valid but its sub-window [1, -1] is not, while another sub-window [3] is.

2. In longest substring without repeating characters, why left = last[c] + 1 only when last[c] >= left?

Answer

An earlier occurrence before left is already outside the window and does not create a repeat. Moving left backward would re-admit characters that were evicted for a reason and could produce a window with repeats ("abba" would answer 3 instead of 2).

3. How many pointer moves does the variable window make in the worst case, and why does that bound the running time?

Answer

At most : right moves times and left moves at most times because it never decreases and never passes right + 1. Each move does summary work (or expected with a hash map), so the total is despite the nested loop.

4. Why is exactly(k) = atMost(k) - atMost(k-1) correct?

Answer

Every subarray with at most distinct values has either exactly or at most , and not both. The two sets partition atMost(k), so subtracting the count of one leaves the count of the other.

5. A fixed-size window of length over an array with negative numbers — does the "fixed windows do not need monotonicity" claim really hold? Why?

Answer

Yes. The fixed window computes the exact sum of every window of length by adding one element and subtracting another; no decision depends on the sum's sign or monotonicity. Monotonicity only matters when the algorithm chooses the window size using the predicate. [1, -1, 5, -2, 3, -3] with gives sums 0, 4, 3, 1, 0 and maximum 4, exactly.

Further reading / sources

  • Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 4th ed. — Chapter 16, "Amortized Analysis" (Chapter 17 in the 3rd edition; the aggregate and accounting methods used for the bound), and §32.2 (Rabin–Karp, a rolling-hash fixed window).
  • Steven Skiena, The Algorithm Design Manual, 3rd ed. — Chapter 3, "Data Structures" (the hash tables and deques used as window summaries).
  • cp-algorithms, Two pointers technique — the competitive-programming view of windows as two pointers.
  • Jon Postel (ed.), RFC 793, Transmission Control Protocol (1981), §3.7 "Data Communication" — the sliding-window flow-control mechanism; RFC 7323 (window scaling).
  • Jacob Ziv and Abraham Lempel, "A Universal Algorithm for Sequential Data Compression", IEEE Transactions on Information Theory 23(3), 1977 — the sliding-window dictionary (LZ77).
  • Deutsch, RFC 1951, DEFLATE Compressed Data Format Specification (1996) — the 32 KB window.
  • Apache Flink documentation, "Windows" — tumbling, sliding and session windows in a production stream processor.

Lessons: previous — Two Pointers · next — Prefix Sums & Difference Arrays · module — Linear Data Structures.

Related Archon pages: Monotonic Stack & Deque · Queues, Deques & Circular Buffers · Hash Tables · Strings in Depth · Rate Limiting · How to Solve Any Problem · Testing & Debugging Algorithms.