Variable-Size Window

Variable-size sliding window is the more powerful half of the pattern. The window length isn’t fixed — it grows and shrinks based on whether the current contents are valid under some problem-specific predicate.

There are two genuine pointers, l (left edge) and r (right edge), and they move at different speeds:

r advances every iteration of the outer loop (always one step forward).
l advances only when the window becomes invalid, and keeps advancing until validity is restored.

That asymmetric motion is what makes the technique O(n) overall — each element enters the window at most once (r advances) and leaves at most once (l advances). Total work: O(2n) = O(n).

The expand-contract template

l = 0
state = empty
answer = identity

for r in 0 .. n - 1:
    add(state, nums[r])                  # expand right

    while state is INVALID:
        remove(state, nums[l])           # contract left
        l += 1

    answer = update(answer, l, r, state) # record the current valid window

That’s the whole template. Three things vary problem-to-problem:

What state is (sum, count of distinct, hash map, etc.).
What “invalid” means (sum exceeds target, more than k distinct, duplicate present, etc.).
What you record (r − l + 1 for longest, r − l + 1 for shortest just when valid, a running count, etc.).

The inner while loop is the secret. It looks like it makes the algorithm O(n²), but it doesn’t — l only ever moves forward, never backwards, across the whole input. So the total number of inner-loop iterations across all outer iterations is at most n.

Variant A — “Longest valid window”

The most common shape. “Find the longest contiguous subarray such that the contents satisfy property P.”

The window is always valid by the time you update the answer (because the while loop just finished shrinking it back into validity). So the current window length r − l + 1 is a candidate answer at every iteration.

Worked example: Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters.

State: a set of characters in the window (or a frequency map). Invalid when: the just-added character s[r] is already in the set. Record: r − l + 1 after the shrink loop.

Time: O(n). Space: O(min(n, charset)).

Worked example: Longest Substring with At Most K Distinct Characters

Find the longest substring of s containing at most k distinct characters.

State: a hash map char → frequency. Invalid when: len(map) > k. Record: r − l + 1 after the shrink loop.

Time: O(n). Space: O(k).

Variant B — “Shortest valid window”

The window is allowed to be invalid most of the time. You only record the answer when it becomes valid, then immediately try to shrink further to see if a smaller window also works.

Worked example: Minimum Size Subarray Sum

Given a positive-integer array nums and target target, find the minimal length of a contiguous subarray of which the sum is >= target. Return 0 if no such subarray.

State: the running sum. Valid when: sum >= target. Record: r − l + 1 every time we’re valid, then try to shrink.

Time: O(n). Space: O(1).

Where does the answer update go? In “longest valid”, it’s after the shrink (window is just-barely valid, record its length). In “shortest valid”, it’s inside the shrink loop (every smaller window that’s still valid is a candidate). Get this swap wrong and your answers are off.

Worked example: Minimum Window Substring

Given two strings s and t, return the minimum window in s which contains all characters of t (including duplicates). Return "" if no such window.

This is the boss-level variable-window problem. State is a character frequency map for t, plus a “characters fully satisfied” counter.

State: need[c] = how many more of c we need. matches = how many distinct chars currently have count >= need[c]. Valid when: matches == distinct chars in t. Record: the (l, r) pair of the smallest valid window seen.

Time: O(|s| + |t|). Space: O(|s| + |t|).

The “match counter” trick from the fixed-window page returns here: instead of comparing two hash maps every iteration, we track how many distinct characters have hit their target count, and increment / decrement that counter in O(1) whenever a frequency crosses or moves away from the threshold.

Variant C — “Count of valid windows”

The third common shape: “How many contiguous subarrays satisfy property P?”

The standard move: at every iteration, count how many valid windows end at index r. The total is the sum across all r.

Worked example: Subarrays with Sum Less Than K

Given a positive-integer array nums and integer k, count the number of contiguous subarrays whose sum is strictly less than k.

State: running sum. Invalid when: sum >= k. Count contribution: every time the window is valid, every subarray ending at r that starts at >= l is valid. That’s r − l + 1 of them.

def subarrays_less_than_k(nums, k):
    l = total = count = 0
    for r in range(len(nums)):
        total += nums[r]
        while total >= k and l <= r:
            total -= nums[l]
            l += 1
        count += r - l + 1
    return count

Time: O(n). Space: O(1).

The r − l + 1 increment is the count contribution for the right endpoint at index r. Every valid subarray ends at exactly one r, so summing across all r gives the total.

Putting it all together

Variant	When window invalid	Answer update location	What you record
Longest	shrink until valid	After the shrink loop	`r − l + 1`
Shortest	not allowed; valid means “found one we want”	Inside the shrink loop	`r − l + 1`, but track min
Count	shrink until valid	After the shrink loop	sum of `r − l + 1`

Memorize this table. It’s the difference between the right algorithm with the wrong answer and an actually correct submission.

A subtle gotcha: the shrink condition

For variable-size windows, the shrink loop runs while the window is INVALID (longest/count variants) or while it’s STILL VALID (shortest variant). Mixing those up is the most common subtle bug.

Problem flavor	Shrink while…
”Longest with property P”	`not P(window)` (shrink until P holds)
“Shortest with property P”	`P(window)` (keep shrinking as long as we’re still valid, recording each time)
“Count of subarrays with property P”	`not P(window)` (count once we’re valid)

If your code returns 0 or the whole-array length for every input, the shrink condition is almost certainly flipped.

Quick check

In a variable-size sliding window, why is the inner `while` loop NOT an O(n²) trap?

In a 'longest valid' problem, where do you put the answer update — inside the shrink loop or after it?

For Minimum Window Substring, the 'match counter' trick lets us check window validity in:

Next: the at-most-K trick — the slickest technique in the sliding-window playbook.

Fixed-Size Window The At-Most-K Trick