Hard · Deficit Sliding Window
Understand → Visualise → Practice.
Return the shortest substring containing every required character with multiplicity, or an empty string.
Count how many required characters are still missing. Expand the right edge until nothing is missing, then shrink from the left while the window still covers everything, recording the shortest window.
need[c] = required count of each character; missing = len(required).
Add text[right]: if need was positive, missing decreases; decrement need either way.
While missing == 0, record the window and remove text[left], restoring need and missing if it becomes positive.
O(n + m) time and O(alphabet) space.
Tracking only distinct letters ignores multiplicity: "AA" needs two As.
Read the full guide first: Strings: Frequencies, Matching and Palindromes.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.