题解 | #最小覆盖子串#

题目主要信息：

• 在S字符串中找到包含T字符串所有字符的最小连续子串
• 两个字符串仅包含大小写字母
• 如果S中没有包含T中所有字符的子串，返回空字符串""，若有，则存在唯一最短

具体思路：

• step 1：字符串仅包含大小写字母，则字符集是已知且有限的，那这种情况下我们可以考虑使用哈希表——只需要维护一个哈希表，里面是字符串T的字符为key值，初始化时当字符在T中出现一次则value值减1，后续如果找到就可以将其加回来。
• step 2：依次遍历字符串S，如果匹配则将哈希表中的相应的字符加1。
• step 3：在遍历过程中维护一个窗口，如果哈希表中所有元素都大于0，意味着已经找全了，则窗口收缩向左移动，找最小的窗口，如果不满足这个条件则窗口右移继续匹配。窗口移动的时候需要更新最小窗口，以取得最短子串。
• step 4：如果匹配到最后，窗口left（初始为-1）也没有右移，说明没有找到，返回空串即可。
• step 5：最后使用字符串截取函数，截取刚刚记录下的窗口即可得到符合条件的最短子串。

因此，这道题中使用哈希表的一个重要条件是字符集是确定的。

可以看如下图示：

代码实现：

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\ast n_S+n_T)O(C*n\_S+n\_T)$，其中C为T字符串的字符集大小，本题中为52个字母，$n_{S}n\_S$为字符串S的长度，$n_{T}n\_T$为字符串T的长度
• 空间复杂度：$O(C)O(C)$，哈希表长度不会超过字符串T的字符集大小