76. 最小覆蓋子串

推薦事前閱讀：滑動窗口

思路

現在給定兩個字串s，t，要找到s當中包含t所有字元的最短子字串。
用最樸素的想法，先計算好我們需要的字串出現了幾次，向右擴張邊界，
如果擴張之後可以包含t的所有字元，就移動左邊界，直到不包含為止。
對於後面的j來說，左邊界更左的位置已經不需要考慮了，
因為這些「更左的位置」對應的長度，都比現在找到的參考答案更長。

在上面的方法當中，每次檢查是否滿足條件都需要遍歷 $52$ 個字元，常數時間比較多， 我們能換個角度去想，把 $t$ 的哈希表freq視為欠債表，用一個變數debt紀錄整體欠了多少字元， 在加入時，不論是否為欠的字元，都要將它加到表上，如果是欠的字元，更新debt變數。 在檢查是否合法時，只要debt為 $0$ ，左邊界就有機會縮減，這時再去檢查左邊界是否有所盈餘。

程式碼

1. 滑動窗口

class Solution {
public:
    string minWindow(string s, string t) {
        const int MX = 128;
        int freq[MX]{}, freqRequest[MX]{};
        int m = s.length(), n = t.length();
        for(char ch : t) { // 計算需要多少字元
            freqRequest[ch]++;
        }

        auto canCover = [&]() -> bool { 
            for(int i = 'A'; i <= 'Z'; i++) {
                if(freqRequest[i] > freq[i]) return false;
            }
            for(int i = 'a'; i <= 'z'; i++) {
                if(freqRequest[i] > freq[i]) return false;
            }
            return true;
        };

        int start = -1, len = m + 1;
        for(int i = 0, j = 0; j < m; j++) {
            freq[s[j]]++; // 擴張右邊界
            while(canCover()) {
                if(j - i + 1 < len) { // 可以覆蓋, 計入參考答案
                    len = j - i + 1;
                    start = i;
                }
                freq[s[i++]]--; // 移動右邊界，對於後續的 j 來說, 當前的左邊界更左的位置已經不需要參考了
            }
        }
        return start == -1 ? "" : s.substr(start, len);
    }
};

2. 滑動窗口 優化

class Solution {
public:
    string minWindow(string s, string t) {
        const int MX = 128;
        int freq[MX]{};
        int debt = 0;
        int m = s.length(), n = t.length();
        for(char ch : t) {
            freq[ch]--;
            debt++;
        }

        int start = -1, len = m + 1;
        for(int i = 0, j = 0; j < m; j++) {
            if(freq[s[j]]++ < 0) { // 還之前是負數，代表是欠債需要的字元
                debt--; // 減少債務
            }
            if(debt == 0) { // 已經還清，能列入參考
                while(freq[s[i]] > 0) { // 左邊界的字元有盈餘
                    freq[s[i++]]--; // 縮減左邊界
                }
                if(j - i + 1 < len) {
                    len = j - i + 1;
                    start = i;
                }
            }
        }
        return start == -1 ? "" : s.substr(start, len);
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(1)$