LCR 017.最小覆盖子串

给定两个字符串 s 和 t 。返回 s 中包含 t 的所有字符的最短子字符串。如果 s 中不存在符合条件的子字符串，则返回空字符串 “” 。如果 s 中存在多个符合条件的子字符串，返回任意一个。

https://leetcode.cn/problems/M1oyTv/description/

class Solution {
public:
    unordered_map<char, int> tmap, dymap; //tmap存t中字符出现频率，dymap存滑动窗口中字符频率
    bool check() {
        for(const auto &p : tmap) {
            if(dymap[p.first] < p.second) {
                return false;
            }
        }
        return true;
    }
    string minWindow(string s, string t) {
        
        int requireCount = t.length(); 
        for(char tmp : t) {
            tmap[tmp]++;
        }
        int minLength = INT_MAX;
        int left = 0, right = 0;
        int ansl = -1;
        unordered_map<char, int> tmpMap(tmap.begin(), tmap.end());
        
        while(right < s.length()) {
            dymap[s[right]]++;
             while(check() && left <= right) {
                if (right - left + 1 < minLength) {
                    minLength = right - left + 1;
                    ansl = left;
                }
                if(tmap.find(s[left]) != tmap.end()) {
                    dymap[s[left]]--;
                }
                left++;
            }
            right++;
        }

        return ansl == -1 ? string() : s.substr(ansl, minLength);

    }
};

使用滑动窗口策略。使用两个map分别储存t中字符出现频率和滑动窗口中字符频率。遍历s，只有当滑动窗口中包含了t中所有字符（判断条件为t中字符在滑动窗口中都存在且对应字符数量大于t（因为t中可能一个字符出现多次））才判断是否要更新最小子串长度（满足条件时先判断是否更新长度再更改left）。