leetcode76：最小覆盖子串

题目链接

leetcode

题目描述

给你一个字符串 s 、一个字符串 t ，返回 s 中涵盖 t 所有字符的最小子串。
如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 。

C++ 代码

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;

/*
    滑动窗口

    使用哈希表，统计出 T 中所有字符出现的次数。
    使用两个指针 i, j 扫描整个字符串，统计 [i, j] 之间每种字符出现的次数。
    遍历过程中的操作如下：
    1. 加入 s[i]，更新哈希表；
    2. 检查 s[j] 是否多余。若是，则移除 s[j]。
    3. 判断当前窗口是否已经满足 T 中所有字符。若是，则更新答案。

    时间复杂度：O(m+n*C)
        其中 n 为字符串 s 的长度，m 为字符串 t 的长度，C 为字符集的大小。
    空间复杂度：O(C)
*/
class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> need; // 哈希表，记录 t 中每个字符出现的次数
        for (const char& c : t) {
            need[c]++;
        }

        unordered_map<char, int> window; // 哈希表，记录窗口中的字符
        int left = 0, right = 0; // 滑动窗口的左边界、右边界
        int valid = 0; // 窗口中满足 need 条件的字符个数
        int start = 0, length = INT_MAX; // 最小覆盖子串的开始索引和长度

        while (right < s.size()) {
            // c 是将移入窗口的字符
            char c = s[right++];
            // 更新窗口内数据
            if (need.count(c)) {
                window[c]++;
                if (window[c] == need[c]) {
                    valid++;
                }
            }

            // 判断左侧窗口是否收缩
            while (valid == need.size()) {
                if (right - left < length) {
                    start = left;
                    length = right - left;
                }

                // d 是将移出窗口的字符
                char d = s[left++];
                // 更新窗口内数据
                if (need.count(d)) {
                    if (window[d] == need[d]) {
                        valid--;
                    }
                    window[d]--;
                }
            }
        }

        return length == INT_MAX ? "" : s.substr(start, length);
    }
};

int main() {
    Solution solution;
    vector<string> s_cases = { "ADOBECODEBANC", "a", "a" };
    vector<string> t_cases = { "ABC", "a", "aa" };
    
    for (int i = 0; i < s_cases.size(); i++) {
        string s = s_cases[i];
        string t = t_cases[i];
        string result = solution.minWindow(s, t);

        cout << "Input: s = \"" << s << 
        "\", t = \"" << t << "\"" << endl;
        cout << "Output: " << (result.empty() ? "" : result) << endl;
    }
    
    return 0;
}