forked from fuwutu/LeetCode
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMinimum Window Substring.cpp
More file actions
54 lines (49 loc) · 1.36 KB
/
Minimum Window Substring.cpp
File metadata and controls
54 lines (49 loc) · 1.36 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
class Solution
{
public:
string minWindow(string S, string T)
{
string result;
vector<int> lettercount(256, 0);
for (char c : T)
{
lettercount[c] -= 1;
}
int not_contain = lettercount.size() - count(lettercount.begin(), lettercount.end(), 0);
size_t left = 0;
size_t right = 0;
for (; right < S.size(); right += 1)
{
lettercount[S[right]] += 1;
if (lettercount[S[right]] == 0)
{
not_contain -= 1;
if (not_contain == 0)
{
while (lettercount[S[left]] > 0)
{
lettercount[S[left]] -= 1;
left += 1;
}
result.assign(S, left, right + 1 - left);
break;
}
}
}
while (right < S.size())
{
right += 1;
lettercount[S[right]] += 1;
while (lettercount[S[left]] > 0)
{
lettercount[S[left]] -= 1;
left += 1;
}
if (right + 1 - left < result.size())
{
result.assign(S, left, right + 1 - left);
}
}
return result;
}
};