Description
Find the shortest substring of s containing every character of nonempty t with its required multiplicity. Return an empty string if impossible. Inputs use English letters.
Solution
from collections import Counter
def min_window(s, t):
if not t:
return ''
need = Counter(t)
missing, left = len(t), 0
start, size = 0, len(s)+1
for right, char in enumerate(s):
if need[char] > 0:
missing -= 1
need[char] -= 1
while missing == 0:
if right-left+1 < size:
start, size = left, right-left+1
need[s[left]] += 1
if need[s[left]] > 0:
missing += 1
left += 1
return '' if size > len(s) else s[start:start+size]Examples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
["CABBA","AB"]- Output
"AB"
AB is the first shortest window covering both required letters.
Example 2
- Input
["a","aa"]- Output
""
Two copies of a are required but only one is available.
Example 3
- Input
["aa","aa"]- Output
"aa"
Both occurrences are needed.
Approach
Track remaining required characters; expand until covered, then shrink while coverage holds.
Time & space
O(n + m) time; O(alphabet size) space for string lengths n and m.