Minimum Window Substring

Minimum Window Substring medium

Description

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

The test cases are generated such that the answer is unique.

Examples

> Case 1:
    s = "ADOBECODEBANC",  t = "ABC"
    Output: "BANC"
    Explanation: Minimum window is "BANC" (length 4).
 
> Case 2:
    s = "a",  t = "a"
    Output: "a"
 
> Case 3:
    s = "a",  t = "aa"
    Output: ""
    Explanation: Both 'a's from t must be in the window; "a" has only one.

Constraints

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

State design / Intuition

The variable-length two-pointer (shrink/expand) pattern:

Expand the right pointer until the window contains all characters of t (“valid window”).
Contract the left pointer as far as possible while the window remains valid.
Record the minimum valid window found.
Expand again from the current right.

“Valid” means: every character required by t has sufficient count in the current window. Track this with a need frequency map and a have counter (number of distinct characters meeting their required frequency).

The key trick: when have == len(required), the window is valid. Each character at most enters and exits the window once — O(n) total.

Code

The have == total condition is the right check — not comparing entire maps. Two windows with different absolute character counts can both be “valid” as long as every required character has sufficient count. The have counter tracks only the distinct characters that have reached their required frequency, not the sum of all counts.

Analysis

Time: O(m + n) — each character enters and exits the window exactly once.
Space: O(n) for the frequency maps (bounded by the size of the character set, which is O(1) for ASCII).

Same skin

Find All Anagrams — fixed-size window version of this exact pattern.
Longest Substring Without Repeating Characters — variable window where “valid” means no duplicates.
Longest Substring with At Most K Distinct Characters — variable window with a different validity condition.
Substring with Concatenation of All Words — same idea, but each “character” is a word of fixed length.

Find All Anagrams Longest Palindromic Substring