leetcode 链接：76. 最小覆盖子串

题目

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

输入：s = "a", t = "a"
输出："a"

解答 & 代码

解法一：滑动窗口+两个哈希表

使用滑动窗口的思想，使用双指针，设定一个用于扩展窗口的 right 指针，以及一个用于收缩窗口的 left 指针。
在字符串 s 上滑动窗口：

如果窗口未覆盖字符串 t 的所有字符，则 right 指针右移
如果窗口覆盖了字符串 t 的所有字符，则 left 指针右移

[困难] 76. 最小覆盖子串 - 图1

如何判断当前窗口是否覆盖了字符串 t 的所有字符：设置两个哈希表

注意：字符串 t 中可能有重复字符，因此哈希表还需记录每个字符出现的次数

unordered_map<char, int> tChCntMap：用于存储字符串 t 的各个字符及其出现的次数
unordered_map<char, int> subSChCntMap：用于存储当前窗口包含的各个字符及其出现的次数

遍历哈希表 tChCntMap 的每个字符，如果哈希表 subSChCntMap 中都存在且计数大于等于 tChCntMap 中对应字符的计数，说明当前窗口覆盖了字符串 t 的所有字符，否则就是没覆盖

复杂度分析：

时间复杂度：O()，最坏情况下左右指针对 s 的每个元素都遍历一遍，每次检查当前窗口是否覆盖 t，需要遍历 t 的哈希表，哈希表长最大为 C（C 是字符集大小），因此需要 C|s| 的时间；此外，将 t 中每个字符插入哈希表需要时间 |t|

空间复杂度 O(C)：C 是字符集大小，每个哈希表存放的键值对数量不会超过字符集大小

class Solution {
public:
  string minWindow(string s, string t) {
      int sLen = s.size();        // 字符串 s 的长度
      int tLen = t.size();        // 字符串 t 的长度
      if(sLen <= 0 || tLen <= 0 || sLen < tLen)
          return "";

      // 将字符串 t 中的各字符及其出现次数存储到哈希表，提高查找效率
      unordered_map<char, int> tChCntMap;        // 哈希表，存储t中每个字符及其出现的次数
      for(int i = 0; i < tLen; ++i)
      {
          if(tChCntMap.find(t[i]) != tChCntMap.end())
              ++tChCntMap[t[i]];        // 如果哈希表中存在该字符，将其计数+1
          else
              tChCntMap[t[i]] = 1;    // 如果不存在，插入，计数为 1
      }

      int resultLeft = -1;        // 最小覆盖子串的左边界
      int resultRight = sLen;        // 最小覆盖子串的右边界
      int left = 0;                // 当前子串的左边界
      int right = 0;                // 当前子串的右边界
      unordered_map<char, int> subSChCntMap;    // 哈希表，存储当前子串s[left]~s[right]中的每个字符及其出现的次数
      subSChCntMap[s[right]] = 1;    // 将第一个字符存储到哈希表，计数为 1
      // 滑动窗口遍历字符串 s
      while(right < sLen && left <= sLen - tLen)
      {
          // 如果当前子串的长度大于等于目标字串 t 的长度
          if(right - left + 1 >= tLen)
          {
              // 遍历字符串 t 的哈希表，和当前子串的哈希表比较，判断当前子串是否包含了 t 的每个字符
              bool covered = true;    
              for(auto it = tChCntMap.begin(); it != tChCntMap.end() && covered; ++it)
              {
                  if(subSChCntMap.find(it->first) == subSChCntMap.end() || subSChCntMap[it->first] < it->second)
                      covered = false;
              }
              // 如果当前子串未包含 t 的每个字符
              if(covered == false)
              {
                  ++right;            // 子串的右边界往右移动一格
                  if(right >= sLen)    // 如果子串的右边界超出了 s 的右边界，停止滑动窗口
                      break;
                  // 更新子串的哈希表
                  if(subSChCntMap.find(s[right]) != subSChCntMap.end())
                      ++subSChCntMap[s[right]];
                  else
                      subSChCntMap[s[right]] = 1;
              }
              // 如果当前子串包含了 t 的每个字符
              else
              {
                  // 如果当前子串的长度小于最小覆盖子串的长度，更新最小覆盖子串的左右边界
                  if(right - left < resultRight - resultLeft)
                  {
                      resultRight = right;
                      resultLeft = left;
                  }
                  // 子串窗口的左边界往右移动一格，更新子串的哈希表
                  --subSChCntMap[s[left]];
                  ++left;
              }
          }
          // 如果当前子串的长度小于目标字串 t 的长度，则当前子串肯定未覆盖字符串 t 的每个字符
          else
          {
              ++right;            // 子串的右边界往右移动一格
              if(right >= sLen)    // 如果子串的右边界超出了 s 的右边界，停止滑动窗口
                  break;
              // 更新子串的哈希表
              if(subSChCntMap.find(s[right]) != subSChCntMap.end())
                  ++subSChCntMap[s[right]];
              else
                  subSChCntMap[s[right]] = 1;
          }
      }

      // 如果最小覆盖子串的长度小于等于 s 的长度，返回该最小覆盖字串
      if(resultRight - resultLeft <= sLen)
          return s.substr(resultLeft, resultRight - resultLeft + 1);
      // 否则，说明不存在覆盖子串，返回""
      else
          return "";
  }
};

执行结果： ``` 执行结果：通过

执行用时：236 ms, 在所有 C++ 提交中击败了 5.02% 的用户内存消耗：7.6 MB, 在所有 C++ 提交中击败了 75.42% 的用户

<a name="H99Kp"></a>
## 解法二：解法一的改进
在解法一的基础上，先对字符串 `s` 进行预处理，只保留 `s` 中与 `t` 相关的字符，eg. 若 `t="XXABXXCXBAX"`，`t="a"`，只保留 `"ABCBA"`。但是由于还需要统计长度，因此这个预处理的具体做法是设置一个数组 `validIdxList`，存储这些有效字符在 `s` 中的下标，eg. 上面的例子中，`validIdxList="23689"`。然后后续的滑动窗口在数组 `validIdxList` 上做
```cpp
class Solution {
public:
    string minWindow(string s, string t) {
        int sLen = s.size();
        int tLen = t.size();
        if(sLen <= 0 || tLen <= 0 || sLen < tLen)
            return "";

        unordered_map<char, int> tChCntMap;
        for(int i = 0; i < tLen; ++i)
        {
            if(tChCntMap.find(t[i]) != tChCntMap.end())
                ++tChCntMap[t[i]];
            else
                tChCntMap[t[i]] = 1;
        }

        // 设置数组 validIdxList，只存储 s 中有效字符的下标
        vector<int> validIdxList;
        for(int i = 0; i < sLen; ++i)
        {
            if(tChCntMap.find(s[i]) != tChCntMap.end())
                validIdxList.push_back(i);
        }
        int validLen = validIdxList.size();
        if(validLen < tLen)
            return "";

        // 后续的滑动窗口操作，修改为在 validIdxList 上进行
        int resultLeft = -1;
        int resultRight = sLen;
        int left = 0;
        int right = 0;
        unordered_map<char, int> subSChCntMap;
        subSChCntMap[s[validIdxList[right]]] = 1;
        while(right < validLen && left < validLen && validIdxList[left] <= validIdxList[validLen - 1] - tLen + 1)
        {
            if(validIdxList[right] - validIdxList[left] + 1 >= tLen)
            {
                bool covered = true;
                for(auto it = tChCntMap.begin(); it != tChCntMap.end() && covered; ++it)
                {
                    if(subSChCntMap.find(it->first) == subSChCntMap.end() || subSChCntMap[it->first] < it->second)
                        covered = false;
                }
                if(covered == false)
                {
                    ++right;
                    if(right >= validLen)
                        break;
                    if(subSChCntMap.find(s[validIdxList[right]]) != subSChCntMap.end())
                        ++subSChCntMap[s[validIdxList[right]]];
                    else
                        subSChCntMap[s[validIdxList[right]]] = 1;
                }
                else
                {
                    if(validIdxList[right] - validIdxList[left] < resultRight - resultLeft)
                    {
                        resultRight = validIdxList[right];
                        resultLeft = validIdxList[left];
                    }
                    --subSChCntMap[s[validIdxList[left]]];
                    ++left;
                }
            }
            else
            {
                ++right;
                if(right >= validLen)
                    break;
                if(subSChCntMap.find(s[validIdxList[right]]) != subSChCntMap.end())
                    ++subSChCntMap[s[validIdxList[right]]];
                else
                    subSChCntMap[s[validIdxList[right]]] = 1;
            }
        }

        if(resultRight < sLen && resultLeft >= 0)
            return s.substr(resultLeft, resultRight - resultLeft + 1);
        else
            return "";
    }
};

执行结果：

执行结果：通过

执行用时：212 ms, 在所有 C++ 提交中击败了 5.02% 的用户
内存消耗：8.8 MB, 在所有 C++ 提交中击败了 13.05% 的用户