Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".
m == s.length, n == t.length, 1 <= m, n <= 10^5
Use sliding window with character frequency maps. Expand right to include all chars of t, then shrink left to minimize window while maintaining validity.
def minWindow(s, t):
if not t or not s:
return ""
from collections import Counter
dict_t = Counter(t)
required = len(dict_t)
left, right = 0, 0
formed = 0
window_counts = {}
ans = float("inf"), None, None
while right < len(s):
c = s[right]
window_counts[c] = window_counts.get(c, 0) + 1
if c in dict_t and window_counts[c] == dict_t[c]:
formed += 1
while left <= right and formed == required:
c = s[left]
if right - left + 1 < ans[0]:
ans = (right - left + 1, left, right)
window_counts[c] -= 1
if c in dict_t and window_counts[c] < dict_t[c]:
formed -= 1
left += 1
right += 1
return "" if ans[0] == float("inf") else s[ans[1]:ans[2]+1]