76. Minimum Window Substring
## description
## 76. Minimum Window Substring
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 "".
The testcases will be generated such that the answer is unique.
Example 1:
1Input: s = "ADOBECODEBANC", t = "ABC"
2Output: "BANC"
3Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.Example 2:
1Input: s = "a", t = "a"
2Output: "a"
3Explanation: The entire string s is the minimum window.Example 3:
1Input: s = "a", t = "aa"
2Output: ""
3Explanation: Both 'a's from t must be included in the window.
4Since the largest window of s only has one 'a', return empty string.Constraints:
- –m == s.length
- –n == t.length
- –1 <= m, n <= 105
- –s and t consist of uppercase and lowercase English letters.
Follow up: Could you find an algorithm that runs in O(m + n) time?
## notes
### Intuition
Track required character frequencies from t. A window is valid when all frequencies are satisfied (≤ 0 after decrementing). Expand the window to find valid substrings, then shrink to find the minimum.
### Implementation
Build a frequency map of characters in t. Process the first window of size len(t), decrementing counts. Slide the window: when valid (all counts ≤ 0), update the minimum and shrink from the left. When invalid or at minimum size, expand from the right. Update the frequency map appropriately when characters enter or leave the window.
### Edge-cases
Update order matters: when expanding right, decrement AFTER moving. When shrinking left, increment BEFORE moving. Handle the case where no valid window exists (return empty string).
- –Time: O(m) — sliding window across s
- –Space: O(n) — frequency map for characters in t
### Complexity
## solution
1class Solution:
2 def minWindow(self, s: str, t: str) -> str:
3 if len(t) > len(s):
4 return ""
5
6 freq = {}
7 for c in t:
8 freq[c] = freq[c] + 1 if c in freq else 1
9
10
11 l, r = 0, len(t) - 1
12
13 for i in range(len(t)):
14 if s[i] in freq:
15 freq[s[i]] -= 1
16 min_window = ""
17 while r < len(s):
18 is_valid = all(freq[c] <= 0 for c in freq)
19 if is_valid:
20 curr_window = r - l + 1
21 if min_window == "" or curr_window < len(min_window):
22 min_window = s[l:r+1]
23
24 # only slide once we get to minimum length
25 if curr_window == len(t):
26 r += 1
27 if r < len(s) and s[r] in freq:
28 freq[s[r]] -= 1
29
30 # reduce window (always look for better)
31 if s[l] in freq:
32 freq[s[l]] += 1
33 l += 1
34 else:
35 r += 1
36 if r < len(s) and s[r] in freq:
37 freq[s[r]] -= 1
38 pass
39
40 return min_window
41
42
43
44
45if __name__ == "__main__":
46 # Include one-off tests here or debugging logic that can be run by running this file
47 # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
48 solution = Solution()
49