-
Notifications
You must be signed in to change notification settings - Fork 0
/
lc_76
84 lines (69 loc) · 2.17 KB
/
lc_76
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
class Solution {
unordered_map<char, int> my_map;
private:
void initialize_map(const string & t) {
for (int i = 0; i < t.length(); ++i){
auto iter = my_map.find(t[i]);
if (iter == my_map.end()){
my_map[t[i]] = -1;
} else {
my_map[t[i]]--;
}
}
}
bool isAllCharsFound(const string & t){
for (int i = 0; i < t.length(); ++i){
auto iter = my_map.find(t[i]);
if (iter == my_map.end()){
return false;
}
if (my_map[t[i]] < 0) return false;
}
return true;
}
public:
string minWindow(string s, string t) {
initialize_map(t);
int start = 0;
int max_len = 0;
int end = 0;
int i = 0;
string output("");
while (i < s.length()){
if(my_map.find(s[i]) != my_map.end()){
start = i;
end = i;
}
++i;
}
end++;
while (end < s.length()){
if (my_map.find(s[end]) != my_map.end()){
my_map[s[end]]++;
if (isAllCharsFound(t)) {
//Register maxLength
if (end-start+1 > max_len){
max_len = end-start+1;
output = s.substr(start,max_len);
cout<<output<<endl;
}
//Increase start until you find a char in t
while (start <= end){
if (my_map.find(s[start]) != my_map.end()){
my_map[s[start]]--;
break;
}
++start;
}
}
}
++end;
}
if (end-start+1 > max_len){
max_len = end-start+1;
output = s.substr(start,max_len);
cout<<output<<endl;
}
return output;
}
};