力扣 76. 最小覆盖子串

🔗 https://leetcode.cn/problems/minimum-window-substring

题目

• 给定字符串 s 和 t，返回最短的 s 的子串，包含了所有 t 的字符，不存在则返回空
• 题目保证若存在这样的子串，答案唯一

思路

• 记录 t 的字母及频次
• 滑动窗口 right 直到覆盖到所有的 t 字符，再收缩 left，找到符合要求子串，记录其中最短的
• 因为 s 的子串可以包含多个 t 的字符，所以设置了 remain，即需要继续找寻的 t 的字母数，并持续记录 t 的字母及频次

代码

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> hash_t;
        for (auto& ch : t) {
            hash_t[ch]++;
        }

        int l = 0;
        int remain = hash_t.size();
        string ans;
        for (int r = 0; r < s.size(); r++) {
            if (hash_t.find(s[r]) != hash_t.end()) {
                hash_t[s[r]]--;
                if (hash_t[s[r]] == 0) remain--;
            } 
            if (remain == 0) {
                while (l < s.size() && 
                    (hash_t.find(s[l]) == hash_t.end() || 
                     hash_t[s[l]] + 1 <= 0)) {
                        if (hash_t.find(s[l]) != hash_t.end()) hash_t[s[l]]++;
                        l++;
                     }
                     if (ans.empty()) ans = s.substr(l, r-l+1);
                     else if (r - l + 1 < ans.size()) ans = s.substr(l, r-l+1);
            }
        }
        return ans;
    }
};