# 76. Minimum Window Substring

## 1.問題

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

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LNuHfQ4sfks2ImOwboo%2F-LNuIecnUNGpbufzKV8T%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-10-03%20%E4%B8%8B%E5%8D%8810.21.45.png?alt=media\&token=dd48c2b6-481b-48e1-8964-f0918b0d3a7f)

## 2.想法&#x20;

* 提問:
* function header, parameter
* test input
* 說明想法&#x20;
  * 統計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;
    }
};
```
