Hard Shrinkable Window Sliding Window
In plain English: Find the shortest piece of string s that contains every character from string t.
Expand right to satisfy the requirement, then shrink left to minimize. Track how many distinct characters are fully satisfied — when all are satisfied, try shrinking. Classic two-phase sliding window.
Prompt
Given strings s and t, return the minimum window substring of s that contains all characters in t (including duplicates). Return '' if no such window exists.
Try to write it from scratch before scrolling down.
Solution
def min_window(s, t):
from collections import Counter
need = Counter(t)
missing = len(need) # distinct chars still needed
window = {}
l = 0
best = (float('inf'), 0, 0) # (length, start, end)
for r, ch in enumerate(s):
window[ch] = window.get(ch, 0) + 1
if ch in need and window[ch] == need[ch]:
missing -= 1
# shrink from left while valid
while missing == 0:
if r - l + 1 < best[0]:
best = (r - l + 1, l, r)
left = s[l]
window[left] -= 1
if left in need and window[left] < need[left]:
missing += 1
l += 1
return s[best[1]:best[2]+1] if best[0] != float('inf') else ''
# Test: min_window("ADOBECODEBANC", "ABC") == "BANC"
# Test: min_window("a", "aa") == ""