[76]最小覆盖子串

给你一个字符串 S、一个字符串 T 。请你设计一种算法，可以在 O(n) 的时间复杂度内，从字符串 S 里面找出：包含 T 所有字符的最小子串。

示例：

输入：S = "ADOBECODEBANC", T = "ABC"
输出："BANC"

提示：

• 如果 S 中不存这样的子串，则返回空字符串 ""。

• 如果 S 中存在这样的子串，我们保证它是唯一的答案。

  class Solution {
  public:
    string minWindow(string s, string t) {
        int left = 0, right = 0;
        int start = 0;
        int len = INT_MAX;
        unordered_map<char, int> need, window;
        int valid= 0;
        for(char c:t) need[c]++;
        while(right < s.size()){
            char c = s[right];
            right++;
            if(need.count(c)){
                window[c]++;
                if(window[c] == need[c]){
                    valid++;
                }
            }
  
            while(valid == need.size()){
                if(right - left < len){
                    start = left;
                    len = right - left;
                }
                char d = s[left];
                left++;
                if(need.count(d)){
                    if(window[d] == need[d]){
                        valid--;
                    }
                    window[d]--;
                }
            }
        }
        return len == INT_MAX ? "":s.substr(start, len);
    }
  };