Repository navigation
Expand file tree
/
Copy pathMinimumWindowSubstring.cpp
More file actions
80 lines (78 loc) · 1.76 KB
/
Copy pathMinimumWindowSubstring.cpp
File metadata and controls
80 lines (78 loc) · 1.76 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
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
#include <cstdio>
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
string minWindow(string S, string T) {
if (S.empty() || T.empty() || S.length() < T.length()) {
return "";
}
unordered_map<char, int> target;
unordered_map<char, int>::iterator itr;
unordered_map<char, int> cur;
for (int i = 0; i < T.length(); ++i) {
if (target.find(T[i]) == target.end()) {
target.insert(pair<char,int>(T[i], 1));
cur.insert(pair<char,int>(T[i], 0));
} else {
target[T[i]]++;
}
}
int left = 0, right = 0;
int minLeft = 0, minRight = S.length();
int cnt = 0;
S.push_back('$');
bool isFound = false;
while (right < S.length()) {
if (cnt < T.length()) {
itr = cur.find(S[right]);
if (itr != cur.end()) {
//cout << right << " " << S[right] << " " << cnt << endl;
if (itr->second < target[S[right]]) {
++cnt;
}
++itr->second;
}
} else {
isFound = true;
--right;
itr = cur.find(S[left]);
while (itr==cur.end() || itr->second > target[S[left]]) {
if (itr != cur.end()) {
--itr->second;
}
++left;
itr = cur.find(S[left]);
}
//cout << left << " " << right << " " << S[left] << " " << S[right] << endl;
if (right-left < minRight-minLeft) {
minLeft = left;
minRight = right;
}
cur[S[left]]--;
++left;
--cnt;
itr = cur.find(S[left]);
while (left <= right && (itr==cur.end()||itr->second > target[S[left]])) {
if (itr != cur.end()) {
--itr->second;
}
++left;
itr = cur.find(S[left]);
}
//cout << left << endl;
}
++right;
}
if (isFound) {
return S.substr(minLeft, minRight-minLeft+1);
} else {
return "";
}
}
int main() {
string S = "aabdidkcgacaagcb";
string T = "aabc";
cout << minWindow(S, T) << endl;
return 0;
}