forked from sunstick/code-street
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathminimum_window_substring.cpp
More file actions
55 lines (43 loc) · 1.41 KB
/
minimum_window_substring.cpp
File metadata and controls
55 lines (43 loc) · 1.41 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
51
52
53
54
55
/*
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) {
int need[256];
int meet[256];
memset(need, 0, sizeof(need));
memset(meet, 0, sizeof(meet));
for (int i = 0; i < t.size(); i++)
need[t[i]]++;
int min_size = INT_MAX;
string min_str = "";
int start = 0;
int end = 0;
int count = 0;
for (int i = 0; i < s.size(); i++) {
if (need[s[i]] == 0) continue;
meet[s[i]]++;
if (meet[s[i]] <= need[s[i]]) count++;
if (count == t.size()) {
end = i;
while (need[s[start]] == 0 || meet[s[start]] > need[s[start]]) {
meet[s[start]]--;
start++;
}
if (end - start + 1 < min_size) {
min_size = end - start + 1;
min_str = s.substr(start, end - start + 1);
}
}
}
return min_str;
}
};