Core Insight Expand to include new information, then shrink only until the window is valid again.
Common Pitfall Update the best answer only when the window satisfies the problem constraint.
Description
Find the minimum window substring of s that contains all characters of t.
Constraints
- Time Complexity:
O(n) - Space Complexity:
O(n)
Tags
stringsliding-windowhash-maptwo-pointers
Implementation Plan Translate the invariant into these small, testable moves.
- Expand the right edge.
- Update window state.
- Shrink from the left while invalid.
- Record the best valid window.
def minWindow(s, t):
if t == "": return ""
countT, window = {}, {}
for c in t: countT[c] = 1 + countT.get(c, 0)
have, need = 0, len(countT)
res, resLen = [-1, -1], float("infinity")
l = 0
for r in range(len(s)):
c = s[r]
window[c] = 1 + window.get(c, 0)
if c in countT and window[c] == countT[c]:
have += 1
while have == need:
if (r - l + 1) < resLen:
res = [l, r]
resLen = (r - l + 1)
window[s[l]] -= 1
if s[l] in countT and window[s[l]] < countT[s[l]]:
have -= 1
l += 1
l, r = res
return s[l : r + 1] if resLen != float("infinity") else ""