Minimum Window Substring
Module 11 · Sliding Window
Problem
Given strings s and t, return the smallest substring of s that
contains every character of t (with at least t's multiplicity — if
t has two as, the window needs at least two). Return "" if no such
window exists.
Examples
Example 1
Input
s = "ADOBECODEBANC", t = "ABC"Output"BANC"Example 2
Input
s = "a", t = "aa"Output""Explanation. s has only one 'a'
Example 3
Input
s = "a", t = "a"Output"a"Constraints
1 ≤ |s|, |t| ≤ 10⁵ · letters (upper and lower case).
Attempt it first
The module's capstone: it fuses Minimum Size Subarray Sum's shape
(shrink while valid, hunt for shortest) with Permutation in String's
frequency matching (need vs. have counts) — except the window is now
dynamic, not fixed, because t's characters don't have to be
contiguous or exactly len(t) long in s. Define "valid" precisely
before writing anything.