最小覆盖子串

 1string minWindow(string s, string t)
 2{
 3    if(s.size() < t.size()) return "";
 4
 5    std::vector<int> need(128, 0);
 6    std::vector<int> window(128, 0);
 7
 8    // 统计 t 中出现的所有字符种类数量（total_kinds）
 9    int total_kinds = 0;
10    for(char c : t)
11    {
12        if(need[c] == 0) total_kinds++;
13        // 统计 t 中每个字符的出现次数
14        need[c]++;
15    }
16
17    // 窗口的左右边界（窗口是在 s 中进行滑动）
18    int left = 0, right = 0;
19    // 最小覆盖子串的起始字符以及长度
20    int start = 0, min_length = INT_MAX;
21    // 窗口中的满足 t 条件数的字符数量
22    int valid = 0;
23    while(right < s.size())
24    {
25        // 提取右边界字符
26        char c = s[right];
27        // 扩大窗口
28        right++;
29
30        // 只有当 t 中也包含当前字符时
31        // 才进行后续的“更新 window”、“判断有效字符数量”的操作
32        if(need[c] != 0)
33        {
34            // window 数组中对应的字符出现次数加 1
35            window[c]++;
36            // 当 window 中此字符的出现次数与 t 中一样时
37            // 就可以认为这个字符已经满足了条件
38            // 有效字符加 1
39            if(window[c] == need[c])
40                valid++;
41        }
42
43        // 当所有字符都已经满足“出现次数”的条件时
44        while(valid == total_kinds)
45        {
46            // 如果此时子串长度小于之前记录的长度
47            // 就更新最小长度
48            if(right - left < min_length)
49            {
50                start = left;
51                min_length = right - left;
52            }
53
54            char d = s[left];
55            // 左边界收缩
56            left++;
57
58            // 如果当前字符在 t 中出现过
59            if(need[d] != 0)
60            {
61                // 同时如果此字符是一个“满足条件”的字符
62                // 就将有效字符数减 1（因为左边界收缩之后，这个字符就被抛弃了）
63                if(window[d] == need[d])
64                    valid--;
65                // 它在窗口中的出现次数也要减 1
66                window[d]--;
67            }
68        }
69    }
70    // 如果最终 min_length 都没有被改变的话
71    // 说明根本就没有进入循环，此时直接返回空字符串
72    return min_length == INT_MAX ? "" : s.substr(start, min_length);
73}