Minimum Window (Have/Need)

Some window problems want the shortest stretch that meets a requirement: a sum of at least target, or a substring containing every character of t. The loop looks like the longest valid window, with one flip. You shrink while the window is valid and record the answer each time, because every shrink that stays valid is a better answer.

The idea#

The two window types differ in when they shrink and when they record.

	Longest valid window	Minimum window
Shrink while	the window is invalid	the window is valid
Record the answer	after the while loop	inside the while loop, before each shrink
Goal of shrinking	get back to valid	find the smallest valid window

This works because the requirement, once met, stays met as the window grows. So for each end, shrinking from the left until the window breaks finds the shortest valid window that ends there.

That leaves the validity check itself. When the requirement is a set of character counts ("contains all of t, with multiplicity"), comparing two whole counters every step is slow. Use have/need instead:

need = the number of distinct characters in t.
have = how many of those characters currently meet their required count in the window.
have goes up by one at the exact moment a character's window count reaches its required count, and down by one at the moment it drops below.

The window is valid exactly when have == need, an $O(1)$ check.

How to spot it#

The question asks for the smallest stretch. Look for these signals.

"Minimum length / smallest substring or subarray such that ...".
"Contains all characters of t", "is a permutation / anagram of p".
A requirement that, once met, stays met as the window grows (so shrinking from the left until it breaks finds the shortest).

Template#

The template uses the have/need form, since it covers the harder case. For a plain sum, replace the have/need check with the sum condition.

need_count = required count of each character
need = number of distinct required characters
have = 0, start = 0, best = none
for end in range(len(s)):
    add s[end] to window counts
    if its count just reached its quota: have += 1
    while have == need:                    # valid: record, then shrink
        best = shorter of best and window start..end
        remove s[start] from window counts
        if its count just fell below its quota: have -= 1
        start += 1
return best, or "no window" if best is none

Each pointer moves at most n times, so the scan is $O(n)$ .

Exact match: permutation or anagram#

Permutation and anagram problems are a stricter version of the same check. When the window must match p's counts exactly, its size is fixed at len(p). Two ways keep it exact:

Shrink on overflow: after adding s[end], while its count is more than p needs, remove from the left. Then have == need means the window is an exact match.
Fixed size: keep the window at len(p) like a fixed-size window and check have == need each step.

Pitfalls#

Most bugs here come from have drifting out of step with the window.

Updating have in the wrong order when shrinking. When you remove s[start], check whether its count currently equals the quota before you decrement, or compare with < after it. Forgetting have -= 1 on removal entirely leaves have counting characters that left the window.
Counting have on every increment. have changes only when a count crosses the quota exactly. Using >= would add one per extra copy.
need is the number of distinct characters, len(Counter(t)), not len(t).
Recording after the loop. In a minimum window the valid windows exist inside the while loop. After it exits, the window is invalid.
No valid window at all. Use a sentinel length and return "" or 0 when it never changes.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the first one.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Minimum Size Subarray Sum

The state is a running sum. Shrink while window_sum >= target: record the length, subtract nums[start], move start. Return 0 if no window ever qualified.

Hint: Minimum Window Substring

This is the full have/need template. Keep the best (length, start) pair and slice once at the end. If the best length never changed from len(s) + 1, return "".

Hint: Permutation in String

The window must match p exactly, so its size is len(p). Use the fixed-size form or shrink on overflow, and return as soon as have == need. Don't forget have -= 1 when a removed character drops below its quota.

Hint: Find All Anagrams in a String

This is Permutation in String, but you collect every match. Record start when have == need, then move start forward by one, updating have and the counter for the character you drop.

Key takeaways#

Minimum window: shrink while valid and record inside the loop.
have counts characters whose quota is met; the window is valid when have == need.
have changes only when a count crosses its quota, in either direction.
Anagram and permutation checks are have/need on a window of exactly len(p).

Core idea#

Find the shortest window that meets a rule. Shrink while the window is valid, and record the answer inside the loop before each shrink.

Key points#

The requirement, once met, stays met as the window grows.
Every shrink that stays valid gives a better answer.
For character quotas, use have/need instead of comparing whole counters.
need is the number of distinct characters in t, len(Counter(t)).
have counts characters whose window count meets the quota. The window is valid when have == need.
have changes only when a count crosses its quota, in either direction.
Spot it: "minimum length", "smallest substring", "contains all characters of t".

Longest vs minimum window#

	Longest valid window	Minimum window
Shrink while	window is invalid	window is valid
Record	after the while loop	inside the while loop

Template#

need = number of distinct required characters
have = start = 0, best = none
for end in range(len(s)):
    add s[end] to window counts
    if its count just reached its quota: have += 1
    while have == need:                # valid: record, then shrink
        best = shorter of best and window start..end
        remove s[start] from window counts
        if its count just fell below its quota: have -= 1
        start += 1
return best, or "" if best is none

Variants#

Minimum Size Subarray Sum: while window_sum >= target, record, subtract nums[start].
Permutation or anagram: exact match, so the window size is len(p). Shrink on overflow, or keep a fixed size, and check have == need.

Pitfalls#

Wrong order on removal. Compare with < after the decrement, or check equality before it.
Using >= to raise have. That adds one per extra copy.
Recording after the loop. The window is invalid there.
No valid window. Keep a sentinel length and return "" or 0.

Say it in an interview#

"For a minimum window, shrink while valid and record inside the loop."
"Have and need make the validity check O(1)."