Blind 75 · Sliding Window

Minimum Window Substring

Hard

Problem

Given strings s and t, return the smallest substring of s that contains every character of t, counting multiplicity — if t has two a's, the window needs two.
If no such window exists, return the empty string. The answer is guaranteed to be unique when it exists, and the expected solution runs in O(s + t).

Examples

Example 1:
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"

Example 2:
Input: s = "a", t = "a"
Output: "a"

Example 3:
Input: s = "a", t = "aa"
Output: ""
Explanation: one a cannot cover two.

Example 4:
Input: s = "ab", t = "b"
Output: "b"

Constraints

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

Prerequisites

Sliding windows — a left and right edge moving forward only, and the invariant that decides when the left edge advances.
Hash maps or fixed-size counts for what the window currently holds.

How to think about it

1. Grow to Cover, Shrink to Minimise Optimal

Intuition

Two motions, not one: extend the right edge until the window covers everything t needs, then pull the left edge in as far as coverage survives, recording the smallest window each time it does. Coverage is tracked as a single integer of outstanding requirements rather than by comparing maps — that counter is what keeps the whole thing linear.

Algorithm

1. Count what t requires. Set an outstanding counter to t's length.
2. Extend right: if the character was still required, decrement the counter.
3. While the counter is zero, the window covers t — record it if smallest, then release the left character; if that makes it required again, raise the counter.
4. Return the smallest window recorded, or the empty string.

Time & Space

Time O(s + t) — each edge crosses the string once. Space O(1) over a fixed character set.