L10 · Sliding Window II — Variable Size

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

Watch first

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. Because each pointer traverses the array at most once, the total work is O(n) — even though the code looks like a loop inside a loop.

First principles

The templates

Template A — longest window satisfying a condition

def longest_valid(nums):
    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

For longest, you record after restoring validity, so the recorded window is always valid.

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

For shortest, you record while the window is valid and shrink to find something even shorter — the record lives inside the while.

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

Mental model

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.

If you ever find yourself moving right backward, or left past right, you've abandoned the pattern — both indices only ever go up.

The trap

What interviewers actually ask

Variable windows are among the most-asked medium problems because they test the amortisation reasoning, not just code.

• Longest Substring Without Repeating Characters (3) · Medium · Amazon, Adobe, Bloomberg — 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 · Amazon, Google — 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 · Google, Amazon — probes: window validity via (window length − maxfreq ≤ k). Follow-up: why you never need to decrement maxfreq.
• Fruit Into Baskets (904) · Medium · Amazon — probes: 'at most 2 distinct' framed as a story; the K-distinct template. Follow-up: generalise to K baskets.
• Minimum Window Substring (76) · Hard · Meta, Amazon, Uber — 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 · Amazon, Meta — probes: the K-distinct longest template directly.

Universal escalation: "can you prove it's linear?" Have the amortisation argument ready in one sentence.

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: O(n) time, O(min(n, alphabet)) memory. Follow-up — "return the substring itself": track best_left when you update best, then slice.

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 positive integers and a target, return the length of the shortest contiguous subarray whose sum is ≥ target, or 0 if none.

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 a string of uppercase letters and an integer k, you may replace at most k characters; return the longest substring that can be made all one letter.

Insight: a window is valid if (window_length − count_of_most_frequent_char) ≤ k — that difference is how many replacements you'd need. Keep a Counter and the running max frequency; shrink when the window becomes invalid.

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]])   # most common char's count in window
        while (right - left + 1) - maxfreq > k:   # too many replacements needed -> shrink
            count[s[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

Complexity: O(n) time, O(26) memory. Follow-up — "why never decrement maxfreq?": a stale (too-high) maxfreq can only make the window seem valid for longer, never shorter than the true best; since we only ever want a longer answer, an overestimate never lets us record something wrong.

Tradeoff

Where this shows up

Variable windows model rate-limiting and connection throttling: a server keeps a window of recent request timestamps and shrinks it from the left as old requests age out, extending right as new ones arrive — exactly the grow-right/shrink-left shape. TCP's congestion control also maintains a window that grows and contracts based on a validity signal (packet loss), the same expand-until-invalid idea applied to network flow.

Checkpoint

Quiz

Practice queue

+7d / +21d mark spaced-repetition anchors.

• 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).