-
Notifications
You must be signed in to change notification settings - Fork 4
Expand file tree
/
Copy path0076-Minimum-Window-Substring.cpp
More file actions
executable file
·68 lines (59 loc) · 2.05 KB
/
Copy path0076-Minimum-Window-Substring.cpp
File metadata and controls
executable file
·68 lines (59 loc) · 2.05 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
/**
* 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).
*
* Example:
* Input: S = "ADOBECODEBANC", T = "ABC"
* Output: "BANC"
*
* Note:
* - If there is no such window in S that covers all characters in T, return the empty string "".
* If there is such window, you are guaranteed that there will always be only one unique minimum
* window in S.
*/
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
using std::string;
using std::vector;
using std::unordered_map;
class Solution {
public:
string minWindow(string s, string t) {
string res{""};
unordered_map<char, int> charCounts;
// chars count in t, this solution doesn't only consider distinct chars in t, duplicates are
// also counted, which means, if t contains two 'c', window should contain two as well
for (auto &c : t) ++charCounts[c];
int left = 0, right = 0, count = 0, start = 0, min = INT32_MAX;
while (right < s.size()) {
if (--charCounts[s[right++]] >= 0) count++;
// count == t.size() means current left to right contains all chars in t, found a window
while (count == t.size()) {
// update min window info (window (start) index and window size (min))
if (min > right - left) {
min = right - left;
start = left;
}
// slide window left boundary, char count > 0 means new windows doesn't contain all
// chars in t, decrease count
if (++charCounts[s[left++]] > 0) --count;
}
}
return min == INT32_MAX ? "" : s.substr(start, min);
}
};
int main() {
Solution s;
int testId = 1;
vector<vector<string>> sts{
// s, t
{"ADOBECODEBANC", "ABC"},
{"ab", "a"}
};
for (auto &st : sts) {
auto window = s.minWindow(st[0], st[1]);
std::cout << "Case " << testId++ << ": " << window << std::endl;
}
}