-
Notifications
You must be signed in to change notification settings - Fork 0
/
Minimum Window Substring.cpp
35 lines (34 loc) · 1.05 KB
/
Minimum Window Substring.cpp
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
class Solution {
public:
/**
* @param source: A string
* @param target: A string
* @return: A string denote the minimum window
* Return "" if there is no such a string
*/
string minWindow(string &source, string &target) {
// write your code here
int dict[128], mapping[128];
memset(dict, 0, sizeof(dict));
memset(mapping, 0, sizeof(mapping));
for(char c:target) dict[c]++;
int m = source.size(), n = target.size();
int i = 0, j = 0, count = 0, ansl = 0, ansr = 0;
while(i+n <= m) {
if(count < n) {
if(j >= m) break;
if(++mapping[source[j]] <= dict[source[j]]) count++;
j++;
}
else {
if(ansr == ansl || ansr-ansl > j-i) {
ansr = j;
ansl = i;
}
if(--mapping[source[i]] < dict[source[i]]) count--;
i++;
}
}
return source.substr(ansl, ansr-ansl);
}
};