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).
For example, S = "ADOBECODEBANC"
T = "ABC"
Minimum window is "BANC"
.
Note: If there is no such window in S that covers all characters in T, return the emtpy string ""
.
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
思路:涉及到2点: 1. Hash, 保证查找为 O(1). 2. S 中设置两指针,根据长度确定右边指针位置;根据若去掉该字符,则该字符在 window 中出现次数将小于在 T 中出现的次数确定左边指针位置。
class Solution {
public:
string minWindow(string S, string T) {
if(T == "" || S == "") return "";
string s;
int ch[2]['z'+1] = {0};
for(int i = 0; i < T.size(); ++i) ++ch[0][T[i]];
int first = 0, cnt = 0;
for(int second = 0; second < S.size(); ++second) {
if(ch[0][S[second]]) {
if(ch[0][S[second]] > ch[1][S[second]])
++cnt;
++ch[1][S[second]];
}
if(cnt == T.size()) {
while(ch[0][S[first]] == 0 || ch[1][S[first]] > ch[0][S[first]]) {
if(ch[1][S[first]] > ch[0][S[first]])
ch[1][S[first]]--;
++first;
}
string tem = S.substr(first, second-first+1);
if(s == "" || s.size() > tem.size()) s = tem;
--ch[1][S[first++]];
--cnt;
}
}
return s;
}
};