Thinking will not overcome fear but action will.

1
class Solution {
2
public:
3
    string minWindow(string S, string T) {
4
        vector<int> chars(128, 0);  // 用来统计字符串T中每个字符的出现次数
5
        vector<bool> flag(128, false);  // 标记字符串T中哪些字符是有效的，即出现过的字符
6

7
        // 统计字符串T中字符的情况
8
        for (int i = 0; i < T.size(); ++i) {
9
            flag[T[i]] = true;  // 将T中出现过的字符置为true
10
            ++chars[T[i]];  // 记录T中每个字符的出现次数
11
        }
12

13
        int cnt = 0, l = 0, min_l = 0, min_size = S.size() + 1;
14
        // cnt用来统计当前窗口中已经包含了T中的字符数
15
        // l和r分别是滑动窗口的左右边界，min_l和min_size用来记录最小窗口的起始位置和长度
16
        // min_size初始值设置为S的长度+1，确保能找到比S更短的子串
17

18
        for (int r = 0; r < S.size(); ++r) {
19
            if (flag[S[r]]) {  // 如果S中的当前字符在T中出现过
20
                if (--chars[S[r]] >= 0) {  // 更新chars中该字符的计数，并检查是否仍然大于等于0
21
                    ++cnt;  // 如果仍然大于等于0，则表示当前窗口中包含了一个T中的字符
22
                }
23

24
                // 当cnt等于T的长度时，当前窗口已包含T中所有字符
25
                while (cnt == T.size()) {
26
                    // 尝试收缩左边界l，找到最短的子串
27
                    if (r - l + 1 < min_size) {
28
                        min_l = l;  // 更新最小子串的起始位置
29
                        min_size = r - l + 1;  // 更新最小子串的长度
30
                    }
31

32
                    if (flag[S[l]] && ++chars[S[l]] > 0) {
33
                        // 如果收缩左边界后导致当前窗口不再包含所有T中字符
34
                        --cnt;  // 减少cnt
35
                    }
36
                    ++l;  // 收缩左边界
37
                }
38
            }
39
        }
40

41
        // 返回最小子串，如果min_size仍然是初始值，则返回空字符串
42
        return min_size > S.size() ? "" : S.substr(min_l, min_size);
43
    }
44
};

1
class Solution {
2
public:
3
    unordered_map <char, int> ori, cnt;
4

5
    bool check() {
6
        for (const auto &p: ori) {
7
            if (cnt[p.first] < p.second) {
8
                return false;
9
            }
10
        }
11
        return true;
12
    }
13

14
    string minWindow(string s, string t) {
15
        for (const auto &c: t) {
16
            ++ori[c];
17
        }
18

19
        int l = 0, r = -1;
20
        int len = INT_MAX, ansL = -1, ansR = -1;
21

22
        while (r < int(s.size())) {
23
            if (ori.find(s[++r]) != ori.end()) {
24
                ++cnt[s[r]];
25
            }
26
            while (check() && l <= r) {
27
                if (r - l + 1 < len) {
28
                    len = r - l + 1;
29
                    ansL = l;
30
                }
31
                if (ori.find(s[l]) != ori.end()) {
32
                    --cnt[s[l]];
33
                }
34
                ++l;
35
            }
36
        }
37

38
        return ansL == -1 ? string() : s.substr(ansL, len);
39
    }
40
};