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 "".
时间: 2024-03-03 19:47:11 浏览: 89
String常用方法-北大青鸟PPT模板
To solve this problem, we can use the sliding window approach again. Here's the algorithm:
1. Initialize two dictionaries: need and window. need stores the count of each character in t, and window stores the count of each character in the current window.
2. Initialize two pointers left and right to mark the current window, and two variables match and required to track the number of matched characters and the number of required characters respectively.
3. Initialize a variable min_len to a large value and a variable start to 0 to store the start index of the minimum window substring.
4. While the right pointer is less than the length of the string s:
- If the character at s[right] is in need, add it to window and update match and required accordingly.
- While all characters in need are included in window, update min_len and start accordingly, and remove the character at s[left] from window and update match and required accordingly.
- Move the left pointer to the right.
- Move the right pointer to the right.
5. Return the minimum window substring starting from index start and having length min_len, or the empty string if no such substring exists.
Here's the Python code for the algorithm:
```
def min_window(s, t):
need = {}
for c in t:
need[c] = need.get(c, 0) + 1
window = {}
left = right = 0
match = 0
required = len(need)
min_len = float('inf')
start = 0
while right < len(s):
if s[right] in need:
window[s[right]] = window.get(s[right], 0) + 1
if window[s[right]] == need[s[right]]:
match += 1
while match == required:
if right - left + 1 < min_len:
min_len = right - left + 1
start = left
if s[left] in need:
window[s[left]] -= 1
if window[s[left]] < need[s[left]]:
match -= 1
left += 1
right += 1
return s[start:start+min_len] if min_len != float('inf') else ""
```
Example usage:
```
s = "ADOBECODEBANC"
t = "ABC"
print(min_window(s, t)) # Output: "BANC"
```
阅读全文