Variable Windows: Expand and Shrink

Sliding Window, lesson 2 of 3

Variable Windows: Expand and Shrink

The two-pointer template for longest and shortest windows, driven by a validity rule.

13 min, 0 of 3 activities solved

Getting Python ready… examples can run in a moment.

Most window problems don't tell you the size: "the longest substring with at most 2 distinct letters", "the shortest subarray with sum ≥ 7". Here the window is s[left : right + 1], and both edges only ever move forward:

e c e b a
L R            expand: R moves right each step
L   R          window "ece" is valid
L     R        "eceb" has 3 letters: invalid
    L R        shrink: L moves until valid again

Everything hangs on one sentence you should write down before coding:

The window is valid when …

"…it has at most 2 distinct letters." "…its sum is at least target." "…no letter appears twice." Pick what to track so you can check that sentence in O(1): a running sum, a Counter, a set.

Template 1: longest valid window. Expand greedily; when the window breaks the rule, shrink from the left until it's valid again; then record.

left = 0
for right in range(len(s)):
    add s[right] to the window
    while window is invalid:
        remove s[left]; left += 1
    best = max(best, right - left + 1)

Example

Longest substring with at most 2 distinct letters

Watch R=3: adding "b" makes 3 distinct letters, so the loop drops "e" and "c" from the left until the window is "eb". Try "ccaabbb" (answer 5).

Template 2: shortest valid window. Now the rule is something like "sum ≥ target", which gets easier to satisfy as the window grows. Expand until valid, then shrink while it's still valid, recording at every step of the shrink:

left = 0
for right in range(len(nums)):
    add nums[right]
    while window is valid:
        best = min(best, right - left + 1)
        remove nums[left]; left += 1

Example

Shortest subarray with sum ≥ target

Every valid window gets recorded before it shrinks, so the answer ([4, 3], length 2) is never skipped. Return 0 when no window is valid.

Quiz

What does this print?

7

6

5

11

Quiz

The shortest-subarray template above (shrink while sum ≥ target) breaks if nums can contain negative numbers. Why?

Adding an element can lower the sum, so a window that's invalid now may become valid later; shrinking is no longer safe

Python can't compare negative numbers with the target

The window length right - left + 1 becomes negative

It still works, negative numbers are fine

Exercise

Max consecutive ones with k flips

nums holds only 0s and 1s. You may flip at most k zeros to ones. Write longest_ones(nums, k) that returns the length of the longest run of 1s you can make.

Rephrase it as a window: the window is valid when it contains at most k zeros. Find the longest valid window.

longest_ones([1,1,1,0,0,0,1,1,1,1,0], 2)  -> 6