76： minimum-window-substring

最小覆盖字串

题目

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
示例 1：

• 输入：s = “ADOBECODEBANC”, t = “ABC”
• 输出：”BANC”
• 解释：最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、’B’ 和 ‘C’。

示例 2：

• 输入：s = “a”, t = “a”
• 输出：”a”
• 解释：整个字符串 s 是最小覆盖子串。

示例 3:

• 输入: s = “a”, t = “aa”
• 输出: “”

• 解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中，
  因此没有符合条件的子字符串，返回空字符串。

  思路

  滑动窗口

  判断窗口内是否含有目标字符，此处使用哈希表存储。
  再慢慢往右移动右边界，判断，记录最小窗口

  代码

   class Solution {
  public:
      // hash map
      unordered_map<char, int>target,cnt;
      
      bool check() {
        for(const auto& pair:target){
          if(cnt[pair.first]<pair.second){
            return false;
          }
        }
        return true;
      }
      string minWindow(string s, string t) {
          //构建目标哈希表
          for(const auto& c:t){
              target[c]++;
          }
          int l = 0,r = 0;
          int sublen = -1;
          int start = 0,end = 0;
          for(;r<s.size();r++){
              cnt[s[r]]++;
              while(check()){
                  if(sublen==-1||r-l+1<sublen){
                      sublen = r-l+1;
                      start = l;
                      end = r;
                  }
                  cnt[s[l]]--;
                  l++;
              }
          }
          return sublen==-1?"":s.substr(start,end-start+1);
      }
  };

  优化

  可以优化，不记录第一个目标字符之前的字符。