题解 | 最小覆盖子串

class Solution {
public:
    string minWindow(string S, string T) {
        if (S.empty() || T.empty() || S.length() < T.length()) {
            return "";
        }
        
        // 统计T中字符的出现次数
        unordered_map<char, int> need;
        for (char c : T) {
            need[c]++;
        }
        
        // 滑动窗口
        unordered_map<char, int> window;
        int left = 0, right = 0;
        int valid = 0; // 记录窗口中满足need条件的字符个数
        int start = 0, min_len = INT_MAX;
        
        while (right < S.length()) {
            // 右指针移动，扩大窗口
            char c = S[right];
            right++;
            
            // 更新窗口数据
            if (need.count(c)) {
                window[c]++;
                if (window[c] == need[c]) {
                    valid++;
                }
            }
            
            // 当窗口满足条件时，收缩左边界寻找最小窗口
            while (valid == need.size()) {
                // 更新最小子串
                if (right - left < min_len) {
                    start = left;
                    min_len = right - left;
                }
                
                // 左指针移动，收缩窗口
                char d = S[left];
                left++;
                
                // 更新窗口数据
                if (need.count(d)) {
                    if (window[d] == need[d]) {
                        valid--;
                    }
                    window[d]--;
                }
            }
        }
        
        return min_len == INT_MAX ? "" : S.substr(start, min_len);
    }
};

1. 统计需求：使用哈希表need统计T中每个字符的出现次数。
2. 滑动窗口：使用双指针left和right表示当前窗口的左右边界window哈希表记录当前窗口中各字符的出现次数valid变量记录当前窗口中满足T需求的字符种类数
3. 窗口扩展：右指针right向右移动，扩大窗口对于每个新加入的字符，如果它在need中，则更新window计数器当某个字符在窗口中的数量等于在T中的需求数量时，valid加1
4. 窗口收缩：当valid等于need的大小时，说明当前窗口包含了T的所有字符记录当前窗口的起始位置和长度左指针right向右移动，收缩窗口对于移出的字符，如果它在need中，则更新window计数器当某个字符在窗口中的数量不再满足需求时，valid减1
5. 返回结果：遍历完成后，返回记录的最短子串

复杂度分析：

• 时间复杂度：O(n)，每个字符最多被左右指针各访问一次
• 空间复杂度：O(n)，使用了两个哈希表来存储字符计数