LeetCode 76. Minimum Window Substring [Hard] [C++] 解題筆記

這題給定一個字串 S 與 一個字串 T，要求在 S 中找到包含 T 中所有字元的最小子串。

EX:

    

        Input: S = "ADOBECODEBANC", T = "ABC"

        Output: "BANC"

想法:

        這題是經典的 "Sliding Window" 的應用題目，中文也有人稱做 "爬行法"，

因為縮短左邊，延伸右邊不停重複很像爬行的樣子。

首先從簡化的問題開始，如果我們只要求找出包含 T 但不一定要是最短的子串會怎摸做？

直覺想法是從頭掃一遍 S 然後用一個 HaskMap 或是 vector 紀錄 S 中出現的 T 中的字元的次數，

只要 T 中的字元都出現至少一次就可以停止遍歷。

照上述方法我們會得到 "ADOBEC" ，但這顯然不是最短的解，這時我們可以試著縮短左邊的範圍，

例如: "ADOBEC" -> "DOBEC"，這時會發現少了 A 之後又不包含 T 中所有字元了，

因此停止縮短左邊的範圍，繼續向右邊遍歷看看還有沒有 A，"DOBEC" -> "DOBECODEBA" ，

終於又找到 A 了又可以包含 T 中所有字元了，因此再次開始試著縮短左邊範圍，

這次發現 "DOBECODEBA" ->  "ODEBA" 縮到這之後又少了 C 於是繼續往右找還有沒有 C，

"ODEBA" -> "ODEBANC"，終於在最後一個字元又找到C，繼續縮短左邊界，

最終發現 "ODEBANC" -> "ANC" 結束。

我們只需要將在這個過程中出現的可以包含 T 中所有字元的子串比較長短就可以得到答案。

整個過程有點像下面這樣，找到第一個包含 T 的子串之後開始縮短左邊界，

縮到無法包含 T 又開始延伸右邊界，左左右右左左右右，是不是很像在爬行呢?

    "ADOBECODEBANC"   

    "ADOBECODEBANC"   

    "ADOBECODEBANC"   

    "ADOBECODEBANC"

    "ADOBECODEBANC"

    "ADOBECODEBANC"

Complexity: O(n) time, O(n) space.

完整程式碼:

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> m;
        
        for (int i = 0; i < t.size(); i++) {
            m[t[i]]++;
        }
        int left = 0;
        int min_left = -1;
        int match_cnt = 0;
        int min_len = INT_MAX;
        for (int i = 0; i < s.size(); i++) {
            if (--m[s[i]] < 0) { continue; }
            match_cnt++;
            while (match_cnt >= t.size()) {
                if (i - left + 1 < min_len) {
                    min_len = i - left + 1;
                    min_left = left;
                }
                if (++m[s[left]] > 0) { 
                    match_cnt--;
                }
                left++;
            }
        }
        
        return (min_left >=0)? s.substr(min_left, min_len) : "";
    }
};