-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMinimumWindowSubstring.cpp
More file actions
50 lines (41 loc) · 1.44 KB
/
MinimumWindowSubstring.cpp
File metadata and controls
50 lines (41 loc) · 1.44 KB
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
44
45
46
47
48
49
50
/**
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.
*/
class Solution {
public:
string minWindow(string S, string T) {
if (S.size() ==0 || S.size() < T.size()) return "";
int need[256] = {0};
int find[256] = {0};
for (int i = 0; i < T.size(); ++i) {
need[T[i]] ++;
}
int count = 0, resStart = -1, resEnd = S.size();
for (int start = 0, end = 0; end < S.size(); ++ end) {
if (need[S[end]] >0) {
find[S[end]] ++;
if (find[S[end]] <= need[S[end]]) count ++;
}
if (count == T.size()) {
while (find[S[start]] > need[S[start]] || need[S[start]] ==0) {
find[S[start]] --;
start ++;
}
if (end - start < resEnd - resStart) {
resStart = start;
resEnd = end;
}
}
}
return (resStart == -1)? "" : S.substr(resStart, resEnd - resStart +1);
}
};