Return the shortest substring of s that contains every character of t with at least its required multiplicity, or the empty string when impossible.
Before you code
Decide how to know the window is complete: it must hold each required letter at least as many times as t asks. Expand the right end until the counts cover t, then shrink the left end while they still do.
Hints
- Count what t needs, count what the window holds, and track how many distinct required letters are already satisfied.
- Expand until the window is valid, then shrink from the left while it stays valid, recording the shortest valid window seen.
- Duplicate letters in t raise the bar — a window needs two copies of a letter when t asks twice — and when t demands more than s offers, the answer is empty.
Production & complexity notes
When solving Minimum Window Substring on LeetCode (hard), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Sliding window to reinforce the underlying pattern.
What it practices
Expand-then-shrink with a coverage test, from Sliding window.