Two pointers: the first pointer starts at the first character, and we enumerate the second pointer’s position from left to right. Once all target characters are covered, slide the first pointer forward to see if the condition still holds. Find the minimum window that satisfies the condition.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| class Solution {
public:
int letters1[256];
int letters2[256];
string minWindow(string S, string T) {
for(int k = 0;k < 256;k++) {
letters1[k] = 0;
letters2[k] = 0;
}
for(int k = 0;k < T.length();k++) {
letters1[T[k]]++;
letters2[T[k]]++;
}
int min = S.length()+T.length();
int start,end;
int count = T.length();
int i = 0;
for(int j = 0;j < S.length();j++) {
if(letters2[S[j]] > 0) {
letters1[S[j]]--;
if(letters1[S[j]] >= 0)count--;
}
if(count == 0) {
while(true) {
if(letters2[S[i]] > 0) {
if(letters1[S[i]] < 0)
letters1[S[i]]++;
else
break;
}
i++;
}
if(j - i + 1 < min) {
min = j - i + 1;
start = i;
end = j;
}
}
}
if(min == S.length()+T.length())return "";
return string(S,start,end - start + 1);
}
};
|