Sliding Window · 013Hard
Minimum Window Substring
Given strings s and t, return the shortest substring of s that contains every character of t including duplicates. If no such window exists, return "". The answer is guaranteed to be unique.
Constraints
- 1 <= s.length, t.length <= 10^5
- s and t consist of uppercase and lowercase English letters.
Examples
minWindow("ADOBECODEBANC", "ABC") -> "BANC"
minWindow("a", "a") -> "a"
minWindow("a", "aa") -> "" // not enough copies
minWindow("a", "b") -> "" // no window at all
minWindow("aa", "aa") -> "aa" // the whole string is the answer
minWindow("ADOBECODEBANC", "ABBC") -> "BECODEBA" // the second B forces a longer windowEdge cases
- t longer than s — return the empty string.
- Repeated characters in t must each be covered.
- Window characters need not be contiguous in t.
Show the target complexity (spoiler)
- Naive
- O(n^2) time — check every substring against t's character counts.
- Target
- O(n + m) time — expand a window to satisfy the counts, then contract from the left while it stays valid.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/03-sliding-window/013-minimum-window-substring.js ./practice c 013