76. Minimum Window Substring

1.問題

• 給予字串S, T, 尋找S的最小罩窗可以涵蓋T的所有字母

2.想法

• 提問:

• function header, parameter

• test input

• 說明想法

  • 統計t的字母出現個數

  • 移動右邊界, 當t的字母全出現時, 移動左邊界, 一面紀錄最小邊界

• 測試計算複雜度

3.程式碼

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> cnt;
        for (char c : t) {
            cnt[c]++;
        }
        
        string res = "";
        int letterCnt = 0, minLen = INT_MAX, left = 0;
        for (int i = 0; i < s.length(); i++) {
            //移動右邊界, 當涵蓋範圍中目標字母的數量等於t的長度時, 開始縮減左邊界
            if (--cnt[s[i]] >= 0) {
                letterCnt++;
            }
            
            while (letterCnt == t.length()) {
                int len = i - left + 1;
                //計算距離最小距離, 如果比之前小就紀錄距離
                if (len < minLen) {
                    minLen = len;
                    res = s.substr(left, minLen);
                }
                //縮減左邊界, 當縮減時各數少了, 讓長度減一
                if (++cnt[s[left]] > 0) {
                    letterCnt--;
                }
                
                left++;
            }
        } 
        
        return res;
    }
};