力扣 最小覆盖子串

最小覆盖子串

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

题目描述

题目分析f

覆盖子串：首先根据题意，要求目标字符串的元素必须都在子串中出现过，这表明可以是乱序出现。所以在解决问题是我们需要对子串和目标字符串做匹配，查看子串是否符合要求。
$$\begin{array}{rl}\forall & s\in {\mathbf{S}}_{\mathbf{t}}\\ s.t.& s\in \mathbf{Ans}\end{array}$$
比较朴素的思路：采用遍历的方法查看是否任意$s\in {\mathbf{S}}_{\mathbf{t}}$都在$\mathbf{Ans}$中
更好的方法：通过某种表示手段表示子串和目标字符串从而判断$\mathbf{Ans}$是否覆盖${\mathbf{S}}_{\mathbf{t}}$（表示方法判断的复杂度应是$O(1)$）

题目解决

根据题目提示，确定使用滑动窗口的办法。两个注意点，窗口扩大和窗口缩小
当窗口扩大时注意是否满足条件，当满足条件时尝试缩小窗口。注意每当满足条件时，更新最优窗口大小。

遍历覆盖比较法

当满足覆盖时，缩小窗口，一个个判断
代码

class Solution {
public:
    bool is_covered(int cnt_s[], int cnt_t[]) {
        for (int i = 'A'; i <= 'Z'; i++) {
            if (cnt_s[i] < cnt_t[i]) {
                return false;
            }
        }
        for (int i = 'a'; i <= 'z'; i++) {
            if (cnt_s[i] < cnt_t[i]) {
                return false;
            }
        }
        return true;
    }
    string minWindow(string s, string t) {
        int slen = s.size(), tlen = t.size();
        string ans;
        if(slen < tlen) return ans;
        int ansleft = -1, ansright = slen;
        int cntwind[128] = {0}, cntt[128]={0};
        for(char &c : t){
            ++cntt[c];
        }
        int left = 0;
        for(int right = 0; right < slen; ++right){
            ++cntwind[s[right]];
            while(is_covered(cntwind, cntt)){
                if(right - left < ansright - ansleft){
                    ansleft = left;
                    ansright = right;
                }
                --cntwind[s[left]];
                ++left;
            }   
        }
        return ansleft < 0 ? "" : s.substr(ansleft, ansright - ansleft + 1);
    }
};

表示覆盖比较法

通过预先设定窗口表示——$C_u(S_t)$
通过种类，个数的方法表示是否覆盖
实际上通过种类数和个数表示了$S_t$，通过维护cntwind、covered_num判断窗口是否覆盖了$S_t$
融合了哈希和动归的思想

class Solution {
public:
    string minWindow(string s, string t) {
        int slen = s.size(), tlen = t.size();
        string ans;
        if(slen < tlen) return ans;
        int ansleft = -1, ansright = slen;
        int cntwind[128] = {0};

        int covered_num = 0;

        for(char &c : t){
            if(cntwind[c] == 0){
                ++covered_num;
            }
            --cntwind[c];
        }
        
        int left = 0;
        for(int right = 0; right < slen; ++right){
            ++cntwind[s[right]];
            if(cntwind[s[right]] == 0) --covered_num;
            while(covered_num == 0){
                if(right - left < ansright - ansleft){
                    ansleft = left;
                    ansright = right;
                }
                --cntwind[s[left]];
                if(cntwind[s[left]] < 0) ++covered_num;
                ++left;
            }   
        }
        return ansleft < 0 ? "" : s.substr(ansleft, ansright - ansleft + 1);
    }
};

总结，巧妙的通过数字的变化表示了窗口状态的变化
++cntwind[s[right]]; if(cntwind[s[right]] == 0) --covered_num;