# 76. Minimum Window Substring 最小覆盖子串

@TOC

## # 题目描述

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:

``````Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"
``````

Note:

• If there is no such window in S that covers all characters in T, return the empty string "".
• If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

## # 解题方法

### # 滑动窗口

1. 定义 `left`, `right` 分别指向滑动窗口的左右边界，子字符串为 `s[left, right]` 双闭区间。

2. 使用 `right` 指针向右搜索，同时要记录在 `s[left, right]` 这个区间覆盖了多少个 `t` 中的元素。如果在 `s[left,right]` 内，覆盖了所有 t 的元素，说明这个区间是符合要求的一个区间。此时 `right `指针再向右移动已经没有意义。

3. 现在要移动 `left` 指针，直至 `s[left,right]` 子字符串不能覆盖 `t`

``````class Solution {
public:
string minWindow(string s, string t) {
int M = s.size();
int N = t.size();
unordered_map<char, int> scount;
unordered_map<char, int> tcount;
// left and right means [left, right] of s
// count means the same chars of s[left, right] with t
int left = 0, right = 0, count = 0;
int minLen = INT_MAX;
string res;
for (char c : t)
++tcount[c];
while (right < M) {
char c = s[right];
scount[c] += 1;
if (tcount.count(c) && scount[c] <= tcount[c]) {
count += 1;
}
while (left <= right && count == N) {
if (minLen > right - left + 1) {
minLen = right - left + 1;
res = s.substr(left, minLen);
}
char l = s[left];
scount[l] -= 1;
if (tcount.count(l) && scount[l] < tcount[l])
count -= 1;
++left;
}
++right;
}
return res;
}
};
``````

https://leetcode.com/articles/minimum-window-substring/ http://www.cnblogs.com/grandyang/p/4340948.html

## # 日期

2018 年 10 月 3 日 —— 玩游戏导致没睡好，脑子是浆糊。 2020 年 5 月 23 日 —— 这次编辑时对滑动窗口有了更深的理解