# C++实现LeetCode(76.最小窗口子串)

[LeetCode] 76. Minimum Window Substring 最小窗口子串 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).

## [LeetCode] 76. Minimum Window Substring 最小窗口子串

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.

- 先扫描一遍T，把对应的字符及其出现的次数存到 HashMap 中。

- 然后开始遍历S，就把遍历到的字母对应的 HashMap 中的 value 减一，如果减1后仍大于等于0，cnt 自增1。

- 如果 cnt 等于T串长度时，开始循环，纪录一个字串并更新最小字串值。然后将子窗口的左边界向右移，如果某个移除掉的字母是T串中不可缺少的字母，那么 cnt 自减1，表示此时T串并没有完全匹配。

```class Solution {
public:
string minWindow(string s, string t) {
string res = "";
unordered_map<char, int> letterCnt;
int left = 0, cnt = 0, minLen = INT_MAX;
for (char c : t) ++letterCnt[c];
for (int i = 0; i < s.size(); ++i) {
if (--letterCnt[s[i]] >= 0) ++cnt;
while (cnt == t.size()) {
if (minLen > i - left + 1) {
minLen = i - left + 1;
res = s.substr(left, minLen);
}
if (++letterCnt[s[left]] > 0) --cnt;
++left;
}
}
return res;
}
};```

```class Solution {
public:
string minWindow(string s, string t) {
vector<int> letterCnt(128, 0);
int left = 0, cnt = 0, minLeft = -1, minLen = INT_MAX;
for (char c : t) ++letterCnt[c];
for (int i = 0; i < s.size(); ++i) {
if (--letterCnt[s[i]] >= 0) ++cnt;
while (cnt == t.size()) {
if (minLen > i - left + 1) {
minLen = i - left + 1;
minLeft = left;
}
if (++letterCnt[s[left]] > 0) --cnt;
++left;IPennOkLTi
}
}
return minLeft == -1 ? "" : s.substr(minLeft, minLen);
}
};```