Minimum Window Substring

Minimum Window Substring hard

Description

Given two strings s and t, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there’s no such substring, return the empty string "".

The answer is guaranteed to be unique.

Examples

> Case 1:
    s = "ADOBECODEBANC",  t = "ABC"
    Output: "BANC"
    Explanation: "BANC" is the minimum substring containing A, B, C.
 
> Case 2:
    s = "a",  t = "a"
    Output: "a"
 
> Case 3:
    s = "a",  t = "aa"
    Output: ""
    Explanation: both 'a's must be in the window. s only has one.

Constraints

1 <= s.length, t.length <= 10^5
s and t consist of uppercase and lowercase English letters.

State design

The boss-level shortest-valid variable window. The complexity comes from the validity predicate: “the window contains every character of t at least as many times as t does.”

Contiguous range? Yes.
Monotone? Yes — adding a character can only increase or preserve the “have at least one of every needed character” property.
State? Two hash maps: need (frequency in t) and have (frequency in window). Plus a match counter: how many distinct characters in need are currently satisfied.
Valid when: matches == |need|. The match counter avoids comparing two maps every iteration.
Shrink while valid. Record the window length at the start of each shrink step.

Code

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

⚠️

Update matches only when the frequency CROSSES the threshold, not whenever it changes.

On have[c]++: only matches++ when have[c] is now exactly equal to need[c]. Going from 3 to 4 when need[c] = 2 doesn’t add a match — we were already satisfied.
On have[c]--: only matches-- when have[c] is now strictly less than need[c]. Going from 4 to 3 when need[c] = 2 doesn’t lose a match — still satisfied.

Sloppy boundary checks here are the #1 bug in this problem.

Why we shrink while valid

This is a “shortest valid” problem. The window is valid the moment matches == required. To find the smallest valid window, we must try to shrink it. Every step of the shrink is itself a valid (smaller) window worth recording — so the answer update goes inside the shrink loop, not after.

Analysis

Time: O(|s| + |t|) — each character of s enters and leaves the window at most once.
Space: O(|s| + |t|) for the two hash maps in the worst case.

Same skin

Smallest Range Covering Elements from K Lists — variable-size window across multiple sorted lists, same “matches” tracking.
Substring with Concatenation of All Words — the “alphabet” is a multiset of words instead of characters.
Replace the Substring for Balanced String — inverted: find smallest window such that outside it, the character distribution is balanced.

This is the most-asked-about sliding-window problem in interviews. Get the template solid in your head, and ten cousins fall into place.

Subarrays with K Different Integers Sliding Window Maximum