blob: c529687f8e5f4c74493971c3adc4d9e686221340 (
plain)
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
|
#include "leetcode.h"
class Solution {
public:
string minWindow(string s, string t) {
unordered_map<char, int> m1, m2;
int check = INT_MAX;
string ans;
for (char &ch : t)
m1[ch]++;
int slow = 0, fast = 0, count = 0;
for (; fast < s.size(); fast++) {
char c = s[fast];
if (m1.find(c) != m1.end()) {
m2[c]++;
if (m2[c] <= m1[c])
count++;
}
if (count >= t.size()) {
while (m1.find(s[slow]) == m1.end() || m2[s[slow]] > m1[s[slow]]) {
m2[s[slow]]--;
slow++;
}
if (fast - slow + 1 < check) {
check = fast - slow + 1;
ans = s.substr(slow, check);
}
}
}
return ans;
}
};
int main() {
Solution obj;
cout << obj.minWindow("ADOBECODEBANC", "ABC");
}
|