76. 最小覆盖子串

76. 最小覆盖子串

思路1（会超时）

#include<bits/stdc++.h>  
using namespace std;  
typedef long long int64;  
  
class Solution {  
public:  
    bool check(unordered_map<char, int> give, unordered_map<char, int> need) {  
        /**  
         * 检查是否满足条件  
         */        
        for (auto &[k, v]: need) {  
            if (v > give[k]) return false;  
        }  
        return true;  
    }  
  
    string minWindow(string s, string t) {  
        /**  
         * 思路：初始时i,j都在s开头，若不满足，扩大区间（j++），若满足，则缩小区间（i--），这个过程中会存在最小长度的满足条件的区间  
         */        int n = s.length(); // c++ 不能使用int 比较 unsigned        unordered_map<char, int> ct, cs;  
        for (char c: t) ++ct[c];  
        int i = 0, j = -1;  
        int res = s.length() + 1;  
        string r= "";  
        while (j < n) {  
            while (j < n and !check(cs, ct)) {  
                ++cs[s[++j]];  
            }  
            while (j < n and check(cs, ct)) {  
                if (j - i < res) {  
                    res = j - i;  
                    r = s.substr(i,j-i+1);  
                }  
                --cs[s[i++]];  
            }  
        }  
        return r;  
        /*  
         * 然而这样也会超时  
         */    
         }  
};

优化想法：在窗口收缩的时候只需要比较左边被踢出的那个字符，就能剪枝部分运算

class Solution {  
public:  
    static bool check(unordered_map<char, int> &give, unordered_map<char, int> &need, const char toCheck) {  
        /**  
         * 检查是否满足条件  
         */        if (toCheck == '*') {  
            for (auto &[k, v]: need) {  
                if (v > give[k]) return false;  
            }  
        } else if (need[toCheck] > give[toCheck]) {  
            return false;  
        }  
        return true;  
    }  
  
    string minWindow(string s, string t) {  
        /**  
         * 思路：初始时i,j都在s开头，若不满足，扩大区间（j++），若满足，则缩小区间（i--），这个过程中会存在最小长度的满足条件的区间  
         */        int n = s.length(); // c++ 不能使用int 比较 unsigned        unordered_map<char, int> ct, cs;  
        for (char c: t) ++ct[c];  
        int i = 0, j = -1;  
        int res = s.length() + 1;  
        string r= "";  
        while (j < n) {  
            while (j < 0 or (j < n and !check(cs, ct, '*'))) {  
                ++cs[s[++j]];  
            }  
            while (i-1 < 0 ?  (j < n and check(cs, ct, '*')) : (j < n and check(cs, ct, s[i-1]))) {  
                if (j - i < res) {  
                    res = j - i;  
                    r = s.substr(i,j-i+1);  
                }  
                --cs[s[i++]];  
            }  
        }  
        return r;  
        /*  
         * 然而这样也会超时  
         */    }  
};

这样还是会内存超限

最终优化：扁平化

class Solution {  
public:  
    bool check(unordered_map<char, int> give, unordered_map<char, int> need) {  
        /**  
         * 检查是否满足条件  
         */        
         for (auto &[k, v]: need) {  
            if (v > give[k]) return false;  
        }  
        return true;  
    }  
  
    string minWindow(string s, string t) {  
        /**  
         * 思路：初始时i,j都在s开头，若不满足，扩大区间（j++），若满足，则缩小区间（i--），这个过程中会存在最小长度的满足条件的区间  
         */        
         // eg. s:"ADOBECODEBANC", t:"ABC"        
         if (t.empty() or s.empty()) {  
            return "";  
        }  
  
        array<int, 128> need = {0}, window = {0};  
        int required = 0;   // 需要满足的字符的个数  
        for (char c: t) {  
            if (need[c] == 0) {  
                ++required;  
            }  
            ++need[c];  
        }  
        // required: 3;  如果t是"AABC"，则required也为3，只有3种字符  
        int formed = 0; // 已满足的字符的个数  
        int l = 0;  
        int bestLen = INT_MAX, bestL = 0;  
        for (int r = 0; r < (int)s.size(); ++r) {  
            char c = s[r];  
            ++window[c];  
            if (need[c] > 0 and window[c] ==  need[c]) {  
                ++formed;  
            }  
            while (formed == required) {  
                // 已经满足条件了  
                if (r - l + 1 < bestLen) { /* 这个过程会存在最短的区间 */                    bestLen = r - l + 1;  
                    bestL = l;  
                }  
                // 收缩窗口，扔掉最左的字符  
                char cl = s[l];  
                --window[cl];  
                if (need[cl] > 0 and window[cl] < need[cl]) --formed;  
                ++l;  
            }  
        }  
        return bestLen == INT_MAX ? "" : s.substr(bestL, bestLen);  
    }  
};