algorithm/Algorithm/cpp/0076.MinimumWindowSubstring/MinWindow.cpp at master · wuvei/algorithm · GitHub

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    string minWindow(string s, string t) {
        int left = 0, right = 0, need[128] = {}, cnt = t.size();
        int minStart = 0, minLen = INT_MAX;
        for (char c: t) need[c]++;

        for (; right < s.size(); right++) {
            if (need[s[right]] > 0) cnt--;
            need[s[right]]--;
            while(cnt == 0) {
                if (++need[s[left]] > 0) cnt++;
                left++;
                if (cnt > 0 && right - left + 2 < minLen) {
                    minLen = right - left + 2;
                    minStart = left - 1;
                }
            }
        }
        if (minLen != INT_MAX) return s.substr(minStart, minLen);
        return "";
    }
};

// Debug
// class Solution {
// public:
//     void pp (int a[]) {
//         for (int i = 0; i < 128; i++) {
//             if (a[i] > 0) cout << char(i) << ": " << a[i] << " ";
//         }
//         cout << endl;
//     }
//     string minWindow(string s, string t) {
//         int left = 0, right = 0, need[128] = {}, cnt = t.size();
//         int minStart = 0, minLen = INT_MAX;
//         for (char c: t) need[c]++;
//         pp(need);
//         for (; right < s.size(); right++) {
//             cout << "left: " << left << ", right: " << right << ", cnt: " << cnt << endl;
//             if (need[s[right]] > 0) cnt--;
//             need[s[right]]--;
//             pp(need);
//             while(cnt == 0) {
//                 cout << "right: " << right << ", left: " << left << endl;
//                 if (++need[s[left]] > 0) cnt++;
//                 left++;
//                 if (cnt > 0 && right - left + 2 < minLen) {
//                     minLen = right - left + 2;
//                     minStart = left - 1;
//                 }
//             }
//         }
//         if (minLen != INT_MAX) return s.substr(minStart, minLen);
//         return "";
//     }
// };


class Solution2 {
public:
    string minWindow(string s, string t) {
        int left = 0, right = 0, need[128] = {}, cnt = t.size();
        int minStart = 0, minLen = INT_MAX;
        for (char c: t) need[c]++;
        for (; right < s.size(); right++) {
            char cur = s[right];
            if (need[cur] > 0) cnt--;
            need[cur]--;
            while(!cnt) {

                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    minStart = left;
                }
                if (++need[s[left]] > 0) cnt++;
                left++;
            }
        }
        if (minLen != INT_MAX) return s.substr(minStart, minLen);
        return "";
    }
};

int main() {
    string s = "ADOBECODEBANC", t = "ABC";
    Solution sol;
    string ret = sol.minWindow(s, t);
    cout << "ret: " << ret << endl;
    return 0;
}