Minimum Window Substring
The problem
Find the shortest substring of s containing every character of t, including repeated copies. Return an empty string if no such window exists; if t is empty, also return an empty string.
Example
s = "cabefgecdaecf", t = "cae" → "aec"
Need a hint?
Track how many required character copies are still missing.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Count requirements from t. Expand right, reducing the missing count only when a required copy is filled. Once all copies are covered, shrink left while recording the shortest window; stop shrinking when removal creates a deficit. Each pointer moves only forward.
Complexity
O(|s| + |t|) expected time and O(alphabet size) space.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.