题解 | #最小覆盖子串#

思路：

题目的主要信息：

在S字符串中找到包含T字符串所有字符的最小字串
要求时间复杂度 $O(n)$
如果S中没有包含T中所有字符的子串，返回空字符串""，若有有则存在唯一最短

方法一：滑动窗口+哈希表+双指针
具体做法：

维护一个哈希表，里面是字符串T的字符为key值，初始时当字符在T中出现一次则减一。
依次遍历字符串S，如果匹配则将哈希表中的内容加一。
在遍历过程维护一个窗口，如果哈希表中所有元素都大于0，则窗口收缩向左移动，如果不满足这个条件则窗口右移继续匹配。
窗口移动的时候需要更新最小窗口，以取得最短。
如果匹配到最后，窗口left（初始为-1）也没有右移，说明没有找到，返回空串。

最后截取S的窗口返回即可。
图片说明

class Solution {
public:
  bool check(unordered_map<char, int> &hash) { //煎炒是否有小于0的
      for (auto iter = hash.begin(); iter != hash.end(); iter++) {
          if (iter->second < 0)
              return false;
      }
      return true;
  }
  string minWindow(string S, string T) {
      int cnt = S.length() + 1;
      unordered_map<char, int> hash; //记录目标字符串T的字符个数
      for(int i = 0; i < T.length(); i++)
          hash[T[i]] -= 1; //初始化哈希表都为负数，找的时候再加为正
      int slow = 0, fast = 0;  
      int left = -1, right = -1;  //记录左右区间
      for (; fast < S.length(); fast++) {
          char c = S[fast];
          if (hash.count(c))    //目标字符匹配+1
              hash[c]++;
          while (check(hash)) {   //没有小于0的说明都覆盖了，缩小窗口
              if (cnt > fast - slow + 1) { //取最优解
                  cnt = fast - slow + 1;  
                  left = slow;
                  right = fast;
              }
              char c = S[slow];
              if (hash.count(c))
                  hash[c]--; //缩小窗口的时候减1
              slow++;      //窗口缩小
          }
      }
      if (left == -1)     //找不到的情况
          return "";
      return string(S.begin() + left, S.begin() + (right + 1));
  }
};

复杂度分析：

时间复杂度： $O(C*n_S+n_T)$ ，其中C为T字符串的字符集大小， $n_S$ 为字符串S的长度， $n_T$ 为字符串T的长度
空间复杂度： $O(C)$ ，哈希表长度不会超过字符串T的字符集大小

方法二：滑动窗口+双哈希表
具体做法：
建立两个哈希表，hashS记录滑动窗口中各个字符串出现的次数，hashT记录字符串T中各个字符出现的次数。如果hashS包含所有的hashT的字符，并且所有字符次数都不小于hashT，则说明当前窗口能够完全匹配，我们需要找的是其中的最小值。
我们可以遍历S字符串，每次窗口向右移动一步，如果加入了一个新的S[i]，hashS中S[i]的次数还是小于hashT，则当前S[i]是必须的，我们准备一个cnt变量，并加一，用来维护S字符串滑动窗口内满足T字符串的元素的个数。一旦出现左边窗口的字符在HashS中大于hashT，我们将左边窗口往右移动，并使原来的计数减一，因为hashS记录的是滑动窗口中出现的数量，收缩窗口后它就不在滑动窗口了。当cnt=T.length()，即找到了完全匹配，可以更新答案，因为要找到最短窗口，所以还需要继续往右直到遍历结束。

class Solution {
public:
    string minWindow(string S, string T) {
        unordered_map<char, int> hashS;
        unordered_map<char, int> hashT;//记录字符串出现的次数
        string res;
        int cnt = 0;//当cnt=T.length找到
        for(int i = 0; i < T.length(); i++) 
            hashT[T[i]]++;
        for(int i = 0, j = 0; i < S.length(); i++) { //遍历S，i为当前下标，包含窗口起点
            hashS[S[i]]++;   
            if(hashS[S[i]] <= hashT[S[i]]) //找到一个包含字符
                cnt++ ;
            while (hashS[S[j]] > hashT[S[j]]) 
                hashS[S[j++]]--;
            if (cnt == T.length()) {  //找到包含，截取字串
                if (res.empty() || i - j + 1 < res.length())
                    res = S.substr(j, i - j + 1);
            }
        }
        return res;
    }
};

复杂度分析：

时间复杂度： $O(n_S+n_T)$ ，初始化哈希表遍历T字符串，后续又遍历S字符串
空间复杂度： $O(C)$ ，哈希表长度不会超过字符串T和S的字符集大小