The problem
Given strings s and t, return the shortest substring of s that contains every character of t, including repeats (if t has two as, the window needs two).
If no such substring exists, return the empty string "". The answer is unique when it exists.
Examples
- Input
s = "ADOBECODEBANC", t = "ABC"
- Output
"BANC"
- Input
s = "a", t = "a"
- Output
"a"
- Input
s = "a", t = "aa"
- Output
""
Constraints
- 1 ≤ s.length, t.length ≤ 10⁵
- Both consist of uppercase and lowercase English letters.
The idea
Expand a window to the right until it covers t, then shrink it from the left for as long as it still covers t, recording the smallest seen. Then expand again.
Track coverage with need[c] (how many more c are wanted; it goes negative for extras) and missing (how many of t’s characters are uncovered). Adding a character that was wanted lowers missing; removing one that becomes wanted raises it. Each character enters and leaves the window once.
- Time
- O(|s| + |t|)
- Space
- O(1) — 128 counters
Solution · every language run against every case
class Solution: def minWindow(self, s: str, t: str) -> str: need = Counter(t) # how many more of each character the window still needs missing = len(t) # characters of t not yet covered by the window best = (0, 0) # [start, end) of the smallest window found l = 0 for r, c in enumerate(s): if need[c] > 0: missing -= 1 need[c] -= 1 while missing == 0: # the window covers t: shrink it from the left if best == (0, 0) or r + 1 - l < best[1] - best[0]: best = (l, r + 1) need[s[l]] += 1 if need[s[l]] > 0: missing += 1 l += 1 return s[best[0] : best[1]]