Minimum Window Substring

Problem Given strings s and t, return the minimum window substring of s that contains every character of t, including multiplicity. If no such window exists, return the empty string.

Input / Output

• Input: strings s and t.
• Output: the smallest substring of s covering all characters of t (guaranteed unique if it exists).

Constraints

• 1 <= |s|, |t| <= 10^5; expected O(|s| + |t|) — an O(n^2) scan will time out.

Example

• s = "ADOBECODEBANC", t = "ABC" → "BANC"
• s = "a", t = "aa" → "" (multiplicity matters)

Expected approach

• Sliding window with two pointers and a frequency map of t. Expand the right pointer until the window covers t (track a "still-needed" counter), then shrink from the left to minimality before recording. O(|s| + |t|) time, O(alphabet) space.