76. 最小覆盖子串

难度：🔴 Hard | 标签：滑动窗口、哈希 | 状态：⬜ LeetCode 链接

思路

变长滑窗：

• need[c] 是 t 中每字符的需要数；have 是当前窗口已满足的字符种类数
• 右扩：window[c]++，若 window[c] == need[c]，have++
• 当 have == 种类数 时尝试收缩左边界，记录最优
• 收缩时若 window[c] == need[c] 即将破坏，have—

代码

class Solution {
public:
    string minWindow(string s, string t) {
        int need[128] = {}, window[128] = {};
        int kinds = 0;
        for (char c : t) if (need[(int)c]++ == 0) ++kinds;

        int l = 0, have = 0, bestL = -1, bestLen = INT_MAX;
        for (int r = 0; r < (int)s.size(); ++r) {
            int c = s[r];
            window[c]++;
            if (need[c] && window[c] == need[c]) ++have;
            while (have == kinds) {
                if (r - l + 1 < bestLen) { bestLen = r - l + 1; bestL = l; }
                int lc = s[l++];
                window[lc]--;
                if (need[lc] && window[lc] < need[lc]) --have;
            }
        }
        return bestL == -1 ? "" : s.substr(bestL, bestLen);
    }
};

复杂度

• 时间 O(n + m)，空间 O(Σ)

易错 / 回顾

• have 计的是「满足的字符种类」，不是窗口长度
• 收缩条件用 while，不是 if
• 比较 window[c] == need[c] 是 have++/— 的边界，错位一个就 WA