给定一个字符串 S 和一个字符串 T，请在 S 中找出包含 T 所有字母的最小子串。
示例：
输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
说明：
1. 如果 S 中不存这样的子串，则返回空字符串 ""。
2.如果 S 中存在这样的子串，我们保证它是唯一的答案。
代码
class Solution {
public:
string minWindow(string S, string T) {
if (T.size() > S.size()) return "";
string res = "";
int left = 0, count = 0, minLen = S.size() + 1;
unordered_map<char, int> m;
for (int i = 0; i < T.size(); ++i) {
if (m.find(T[i]) != m.end()) ++m[T[i]];
else m[T[i]] = 1;
}
for (int right = 0; right < S.size(); ++right) {
if (m.find(S[right]) != m.end()) {
--m[S[right]];
if (m[S[right]] >= 0) ++count;
while (count == T.size()) {
if (right - left + 1 < minLen) {
minLen = right - left + 1;
res = S.substr(left, minLen);
}
if (m.find(S[left]) != m.end()) {
++m[S[left]];
if (m[S[left]] > 0) --count;
}
++left;
}
}
}
return res;
}
};
