Sliding Window II — Variable Size

Review boundary and corrected contracts

Ordinary longest-valid windows restore actual validity. Character Replacement instead keeps a historical maximum frequency: the current retained window may be invalid. The stored maximum certifies the best length, not the current contents; do not reuse those contents as a witness. Shortest positive-sum windows require nonnegative elements and a positive target.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Own the variable-size window: grow right always, shrink left while invalid, and prove the whole thing is O(n) even though there are two nested-looking loops.

Series: LeetCode — From Basics to Production-Ready · Session 10 / 65 · Phase 1 · Core patterns

Prerequisites. L09 (fixed-size window) strongly recommended — this generalises it. You also need a hash map / set and comfort with a while loop nested inside a for.

What this pattern IS

In L09 the window was rigid — always exactly k wide. But most real questions ask for the longest or shortest window satisfying some condition: the longest substring with no repeated character, the shortest subarray whose sum is at least a target, the longest subarray with at most K distinct values.

Now the window must breathe. You don't know k in advance — you discover it.

The naive approach: try every start, extend as far as valid, record. That's O(n^2) (or worse with per-window checks). The sliding-window insight: a single left pointer and a single right pointer, each only ever moving forward. You grow the right edge to explore, and when the window becomes invalid you nibble the left edge until it's valid again. Pointer progress bounds the number of updates by O(n). Total time is O(n) only when each state update and validity check is bounded-cost (or expected O(n) with suitable hashing). A validity scan over a growing map can add another factor. Safe pointer movement needs a correctness proof independent of this work bound.

A stretchy tape measure over a fence

Real: You drag the right end of a tape along a fence, extending it. When the tape covers something forbidden, you reel in the left end just enough to exclude it, then keep extending right. Each end only moves one direction — you never rewind.

for right in ...: add(nums[right]); while invalid: remove(nums[left]); left += 1; record().

First principles

Question: Why is the variable window O(n) when it has a while loop nested inside a for loop?

Premise: The right pointer advances exactly once per outer iteration: n moves total.

Because: The for right in range(n) loop runs n times and right never moves backward.

Premise: With a valid empty-window state, left increases at most to right+1, never beyond n.

Because: The inner loop only removes elements already included; shrinking to an empty window must stop it. left==right+1 denotes an empty window and is legitimate, for example with an at-most-zero-distinct constraint.

Premise: So across the ENTIRE run, the inner while executes at most n times total, not n times per outer step.

Because: left has only n forward moves available for the whole algorithm — this is amortisation.

Premise: Each add/remove and validity check must have bounded expected cost under suitable keys.

Because: Insert, delete, and lookup in a dict are expected O(1).

Premise: Total work = n right-moves + at most n left-moves + O(1) each = O(n).

Because: Two independent linear budgets, spent once, not multiplied together.

Conclusion: The total number of pointer moves is O(n); combine that with actual callback/key costs. This is an amortized work argument, not a correctness proof or a worst-case constant-hash guarantee.

The templates

Template A — longest window satisfying a condition

def longest_valid(nums, init_state, add, remove, valid):
    left = 0
    best = 0
    state = init_state()               # e.g. a set or Counter of the window
    for right in range(len(nums)):
        add(state, nums[right])        # grow the window to include right
        while not valid(state):        # window broke the invariant -> shrink
            remove(state, nums[left])
            left += 1
        # here the window [left, right] is valid; record its length
        best = max(best, right - left + 1)
    return best

This is a callback-based template: callbacks maintain exactly the current window and must not mutate the input. It applies when validity is preserved by removing leftmost elements, the empty state is valid, and extending an invalid range cannot make that same start valid later. Then earlier rejected starts cannot help later, and shrinking stops at the longest valid suffix for each right endpoint. For examples such as unique characters or at most K distinct values (K>=0), record after restoring actual validity. The historical-maximum replacement optimization below has a different invariant.

Template B — shortest window satisfying a condition

def shortest_valid(nums, target):
    left = 0
    best = float('inf')
    total = 0
    for right in range(len(nums)):
        total += nums[right]           # grow
        while total >= target:         # window is valid -> try to shrink for a shorter one
            best = min(best, right - left + 1)   # record BEFORE shrinking
            total -= nums[left]
            left += 1
    return best if best != float('inf') else 0

This numeric template requires nonnegative elements and a strictly positive target. When a range reaches the target, record it before removing its left endpoint. Any later range with that same start is longer, so it cannot improve the shortest result; removed starts already have their best candidate recorded. Once the sum falls below target, further removal cannot restore it, so extend right. With target <= 0 the empty window needs a separate contract and the printed loop is unsafe; negative elements also invalidate this stopping rule.

The mirror is the key mental split: longest records outside the while; shortest records inside it.

Mental model

Name: Grow right, shrink left

Picture: A caterpillar: the head (right) always crawls forward; when the body breaks a rule, the tail (left) catches up just enough. Both ends only move forward. Length = right − left + 1.

• right advances every outer iteration, unconditionally.

• while the window is INVALID (longest) or VALID (shortest), move left.

• longest: record after the while (window valid). shortest: record inside the while.

• Both pointers monotonically increase → O(n) pointer moves; include update/check costs to obtain total time.

Trigger: A contiguous-range objective suggests investigating a window. Verify its extension/removal properties; the words longest, shortest or exactly K do not establish them.

Memory / mnemonic

Carry the caterpillar and one placement rule: "LONGest records LATE, SHORTest records SOON."

• Longest → the check that shrinks fires when the window is bad; by the time you record, it's good again → record after the while (late).
• Shortest → the while fires when the window is good, and you're squeezing it smaller → record inside the while (soon), then shrink.

The pointer rhyme: "right runs the loop, left chases the rule." Right is driven by the for; left is driven by the invariant.

Neither boundary moves backward in these templates. left may equal right+1 for an empty window; that does not violate forward progress. Moving farther would remove elements not yet added.

The trap

Myth: A while loop inside a for loop is O(n^2), so the variable sliding window is quadratic.

Truth: The pointer moves total O(n) under the template’s contracts. State maintenance can still be more expensive: hashing is expected, and recomputing a full-map maximum inside each iteration is not automatically constant-time.

Why: Amortisation: you count left's moves over the entire algorithm, not per outer step. left advances at most n times total, independent of how the for loop iterates.

Test: Instrument a counter that increments on every left += 1 and every outer step. On any input, both counters stay ≤ n. Their sum is ≤ 2n = O(n).

What reviewers actually ask

These practice selections exercise different window invariants and aggregate-cost arguments; no frequency ranking is claimed.

• Longest Substring Without Repeating Characters (3) · Medium · Practice selection. — probes: variable window + a last-seen map; can you jump left correctly? Follow-up: at most K distinct characters.
• Minimum Size Subarray Sum (209) · Medium · Practice selection. — probes: the shortest-window template with record-before-shrink. Follow-up: what if numbers can be negative (window breaks — use prefix + something else, L12)?
• Longest Repeating Character Replacement (424) · Medium · Practice selection. — probes: window validity via (window length − maxfreq ≤ k). Follow-up: why you never need to decrement maxfreq.
• Fruit Into Baskets (904) · Medium · Practice selection. — probes: 'at most 2 distinct' framed as a story; the K-distinct template. Follow-up: generalise to K baskets.
• Minimum Window Substring (76) · Hard · Practice selection. — probes: shrink with a need-map and a satisfied counter; the boss of the pattern. Follow-up: multiple valid windows, or streaming input.
• Longest Substring with At Most K Distinct Characters (340) · Medium · Practice selection. — probes: the K-distinct longest template directly.

For each selection, explain both why discarded starts cannot improve the result and how many state operations occur. These are separate obligations.

Worked solutions

1. Longest Substring Without Repeating Characters (3)

Plain words: find the length of the longest substring of s that contains no repeated character.

Brute force: check every substring for uniqueness — O(n^2) substrings times O(n) check = O(n^3), or O(n^2) with a set per start. Insight: keep a set of the current window's characters; when the entering char is already present, shrink from the left until it's gone.

def lengthOfLongestSubstring(s):
    seen = set()
    left = 0
    best = 0
    for right in range(len(s)):
        while s[right] in seen:        # entering char duplicates -> shrink
            seen.remove(s[left])
            left += 1
        seen.add(s[right])             # now safe to add
        best = max(best, right - left + 1)   # record (longest -> after the shrink)
    return best

Complexity: expected O(n) time under bounded-cost character hashing, O(min(n, alphabet)) state. The set loop retains the longest unique suffix after shrinking; recording across all right boundaries therefore finds the optimum. To return a substring, retain the best start and slice once at the end, adding O(answer length) output work/storage.

Goal: Use a last-seen-index map to jump left in one move instead of nibbling one char at a time.

Hint: Store last[char] = index; on a repeat, set left = max(left, last[char] + 1).

def lengthOfLongestSubstring(s):
    last = {}
    left = best = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1        # jump past the previous occurrence
        last[ch] = right
        best = max(best, right - left + 1)
    return best

2. Minimum Size Subarray Sum (209)

Plain words: given nonnegative bounded integers and a strictly positive target, return the shortest nonempty contiguous range with sum at least target, or 0 if none. The usual exercise uses positive values; zeros also satisfy this proof. Empty input returns 0.

Insight: grow right to reach the target; once reached, shrink left greedily to find the shortest still-valid window — record inside the while.

def minSubArrayLen(target, nums):
    left = 0
    total = 0
    best = float('inf')
    for right in range(len(nums)):
        total += nums[right]           # grow
        while total >= target:         # valid -> try shorter
            best = min(best, right - left + 1)   # record before shrinking
            total -= nums[left]
            left += 1
    return best if best != float('inf') else 0

Complexity: O(n) time, O(1) memory. Follow-up — "what if values can be negative?": the window no longer has the monotonic property (adding elements can decrease the sum), so this breaks — switch to prefix sums + a monotonic structure or a different method (L12).

3. Longest Repeating Character Replacement (424)

Plain words: given uppercase ASCII letters A–Z and integer k>=0, return the maximum achievable substring length after replacing at most k characters. The function returns a length, not the contents of a valid best window; empty input returns 0.

For an actual window, validity is length - current_max_frequency <= k. The optimized code instead keeps a nondecreasing historical maximum F and shrinks only when length - F > k. That is an optimistic capacity check, not a certificate of the retained window’s actual validity. For example, after AABABBA with k=1, the retained window can be ABBA with F=3, even though it needs two replacements.

from collections import Counter
 
def characterReplacement(s, k):
    count = Counter()
    left = 0
    maxfreq = 0
    best = 0
    for right in range(len(s)):
        count[s[right]] += 1
        maxfreq = max(maxfreq, count[s[right]])   # historical maximum frequency; not necessarily current window frequency
        while (right - left + 1) - maxfreq > k:   # exceeds historical length capacity, not exact validity
            count[s[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

Why the historical maximum is safe for the length only:

1. An addition increases length by one and F by at most one. The previous length was at most F+k, so at most one removal is needed; the retained length never decreases.
2. When F increases, some character really occurs F times in the current window. The new length is at most F+k, so that window is genuinely feasible. While F stays fixed, no shrinking is needed until the length first reaches F+k. Any growth to a new length before that point keeps those F occurrences, supplying a genuine feasible witness for every new record.
3. Once length reaches F+k, later steps at the same F can shrink and retain invalid contents, but cannot increase the recorded length. Another increase in F reestablishes a real witness as in step 2. Thus a stale value never creates an unattainable new best length.
4. Since F is at least the current maximum, any range rejected by length-F>k is truly invalid. Extending that same start cannot lower its required replacements: length increases by one while the actual maximum rises by at most one. Removing it cannot skip an optimum.

Expected O(n) time with bounded-character Counter operations and O(26) state. Do not return the final retained substring as a witness. Recompute actual maximum frequency or separately capture a verified record window if contents are required. “An overestimate is always safe” is not a valid proof for another optimization.

4. Fruit Into Baskets (904) — at most K distinct values

Plain words: choose one contiguous run of trees. Each basket can hold arbitrarily many fruits of one type, so two baskets mean at most two distinct types, not two fruits. Generalize the same task to K baskets: return the maximum window length, not the number of qualifying windows. For characters the identical mechanism solves Longest Substring with At Most K Distinct Characters (340).

Contract. nums is a finite indexable sequence of bounded integer fruit types (or individual characters), with stable hash/equality behavior; the input is not mutated. k must be a nonnegative built-in Python int: this implementation raises TypeError for other types, including bool, and ValueError for negative integers. Empty input returns 0. For k=0, only the empty window is valid, so the result is 0 even for nonempty input; left may become right+1. K larger than the number of types permits the whole input.

Brute force enumerates all ranges and counts their distinct values with a fresh set. The optimized state is a dictionary of positive counts in the current window. Increment the entering type. While there are more than K keys, decrement the leaving type and delete its key exactly when the count reaches zero, then advance left. Only after that loop has restored validity may the longest-window answer be updated.

def longest_at_most_k_distinct(nums, k):
    if type(k) is not int:
        raise TypeError("k must be a built-in int, not bool")
    if k < 0:
        raise ValueError("k must be nonnegative")
    counts = {}
    left = 0
    best = 0
    for right, value in enumerate(nums):
        counts[value] = counts.get(value, 0) + 1
        while len(counts) > k:
            leaving = nums[left]
            counts[leaving] -= 1
            if counts[leaving] == 0:
                del counts[leaving]
            left += 1
        best = max(best, right - left + 1)
    return best
 
 
def totalFruit(fruits):
    return longest_at_most_k_distinct(fruits, 2)

Invariant and safe discard. After each removal, the map still describes exactly [left, right], with no zero-count keys. Thus len(counts) is its actual distinct count, not a historical count of types seen. Removing from the left cannot increase this count. An invalid start has more than K types; extending that same start later cannot remove any of them, so discarding it cannot lose an optimum. The loop stops at the earliest still-eligible valid start for this right endpoint. Recording that longest valid suffix over every right endpoint therefore returns the maximum length. With k=0, removing the newly added last item empties the map and stops shrinking safely; no not-yet-added element is accessed.

Trace [1, 2, 1, 3] with k=2: the first three trees give counts {1: 2, 2: 1} and best 3. Adding 3 gives three keys. Removing the first 1 leaves {1: 1, 2: 1, 3: 1}, still invalid; removing 2 deletes its zero-count key and leaves {1: 1, 3: 1}, a valid length-2 suffix. Best stays 3. A single if removal would stop too early here. Keeping a zero-count key would make dictionary length disagree with distinct types, potentially shrinking beyond the added input. Recording before shrink could falsely accept all four trees. Returning only the final window length would lose the earlier best.

Every element enters once and leaves at most once: O(n) state operations and expected O(n) time under bounded-cost suitable hashing. The map has at most K keys after shrinking and at most K+1 just after an addition, so auxiliary storage is O(min(n, K+1)) entries, including that transient invalid state; this is O(1) for two baskets. No input slice is needed by the implementation.

Self-tests: totalFruit([1, 2, 1]) == 3, totalFruit([1, 2, 1, 3]) == 3, longest_at_most_k_distinct("eceba", 2) == 3, and longest_at_most_k_distinct([1], 0) == 0. Empty input returns 0 for every valid K; negative K is rejected even on empty input. Independently enumerate short sequences and every candidate [i, j) range, retain those with len(set(nums[i:j])) <= k, and compare their maximum length with the function. This is a length oracle: do not subtract these maxima to count exactly-K windows. The separate counting identity in Tradeoff uses at-most counts, not this helper's result.

Tradeoff

Decision: Find a longest/shortest contiguous window under a condition.

Name: Brute force all substrings

Gain: Obviously correct; trivial to reason about.

Cost: Quadratic candidate ranges, potentially cubic total character checks; elapsed limits depend on environment and input.

Pick: Only as a reference oracle to test the fast version.

Name: Variable sliding window

Gain: Linear pointer progress and potentially expected O(n) total work when the state operations and correctness invariant support it.

Cost: Requires a task-specific safe-discard argument. Ordinary longest-valid windows, shortest-cover windows and historical-capacity optimizations do not share one interchangeable invariant.

Pick: Whenever growth/shrink has a monotone effect (all-positive sums, distinct-count, replacement count).

Name: Prefix sums + hashmap

Gain: A prefix-count map handles arbitrary-sign exact-sum counting; other prefix problems may require ordered structures rather than a hash map.

Cost: O(n) memory; conceptually heavier.

Pick: An algebraic prefix relationship supports the required lookup, as with exact sums including negative values; prove that relationship rather than selecting by keyword.

Verdict: Analyze the property. Negative numbers break the simple sum-threshold proof, not every window algorithm. Exactly K distinct values can be counted as atMost(K)−atMost(K−1): an at-most-K window contributes right-left+1 valid ending ranges after shrinking, and the difference removes those with fewer than K distinct values. For 'aba', atMost(2)=6 and atMost(1)=3, so exactly two distinct values occur in 3 ranges: 'ab', 'ba' and 'aba'. This is a window method, not a reason to abandon windows for every exact-count problem.

Where this shows up

An ordered queue of request timestamps can expire old entries from the front as time advances. That resembles forward-moving window boundaries, but a real limiter still needs an exact time boundary, clock policy, state bound and atomic updates. One arrival can expire many entries, giving amortized rather than necessarily worst-case constant processing. TCP's congestion window is a separate network-control concept, not a longest-valid-substring algorithm or a consequence of this proof.

Checkpoint

You can now…

• Write the longest-window and shortest-window templates from a blank file.

• Place the record statement correctly: after the while for longest, inside it for shortest.

• Explain the amortised-O(n) argument in one sentence.

• Recognise when a validity condition is monotonic enough for a window to work.

• Solve longest-no-repeat with both the nibble and the jump variants.

• Identify which sum windows need nonnegative values, and when exact counts can use a difference of at-most counts.

Quiz

Self-check (answer follows each question).

Recall check

Q: For a LONGEST-window problem, where does the record statement go relative to the shrink loop?

A: For the ordinary longest-valid template, after restoring actual validity. The historical-max Character Replacement optimization instead certifies a best length; its retained contents need not be valid.

Q: For a SHORTEST-window problem, where does the record statement go?

A: Inside the while, before shrinking, because the window is valid there and you want the smallest valid one.

Q: Give the one-sentence proof that the variable window is O(n).

A: There are at most n additions and n removals; if each update and validity check is bounded-cost, total work is O(n), or expected O(n) with suitable hashing. Pointer progress alone does not bound arbitrary callback work.

Q: In Longest Repeating Character Replacement, what makes a window valid?

A: Actual window length minus its current maximum character count must be at most k. The shown historical maxfreq can exceed that current count, so its condition is only an optimistic length-capacity test; the separate record-growth proof makes the returned length correct.

Q: Why does the all-positive Minimum Size Subarray Sum break when negatives are allowed?

A: Adding an element can decrease the sum, so validity isn't monotonic — you can't safely stop shrinking, and the window logic fails.

Q: ★ Stretch: in the last-seen-index variant of Longest Substring Without Repeating, why is left = max(left, last\[ch] + 1) and not just left = last\[ch] + 1?

A: Because last[ch] might point to an occurrence that's already behind the current left edge; taking the max prevents left from jumping backward, preserving the monotonic-forward invariant.

Stretch: true

Practice queue

+7d / +21d are optional elapsed-day review suggestions.

• Longest Substring Without Repeating Characters (3) — Medium · the archetype · +7d anchor.
• Minimum Size Subarray Sum (209) — Medium · shortest-window template.
• Fruit Into Baskets (904) — Medium · at-most-2-distinct.
• Longest Repeating Character Replacement (424) — Medium · validity via maxfreq · +21d anchor.
• Longest Substring with At Most K Distinct Characters (340) — Medium · K-distinct longest.
• Max Consecutive Ones III (1004) — Medium · flip at most k zeros.
• Minimum Window Substring (76) — Hard · the boss (full treatment in L11).

Corrective source notes

• collections — Container datatypes — Python 3.14.8 documentation — Counter equality in Python 3.10+ treats missing keys as zero counts. Checked 2026-10-07.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.