76. 最小覆盖子串

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

示例 1：
输入：s = “ADOBECODEBANC”, t = “ABC”
输出：“BANC”

**

示例 2：
输入：s = “a”, t = “a”
输出：“a”

提示：

  • 1 <= s.length, t.length <= 10
  • s 和 t 由英文字母组成

进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？

解题思路

滑动窗口

  1. class Solution {
  2. public:
  3.     string minWindow(string s, string t) {
  4.         unordered_map<char,int>need;//t字符串
  5.         unordered_map<char,int>window;//滑动窗口里包含的t里每个字符及其数量
  6.         for ( char c : t) need[c]++;
  7.         int left = 0,right = 0;//滑动窗口的左右边界
  8.         int valid = 0;//表示window内包含t所需的个数
  9.         int start = 0,len = INT_MAX;
  10.         while (right < s.size()) {//[left,right)
  11.             char c = s[right];//c是将移入窗口的字符
  12.             right++;//右移窗口
  13.             //进行窗口内一系列数据的更新
  14.             if (need.count(c)) {//c属于t里的字符
  15.                 window[c]++;
  16.                 if (window[c] == need[c])
  17.                     valid++;
  18.             }
  19.             //判断左侧窗口是否要收缩
  20.             while (valid == need.size()) {
  21.                 //在这里更新最小覆盖子串
  22.                 if (right - left < len) {//可能有多个满足的len,要取最小的
  23.                     start = left;
  24.                     len = right - left;
  25.                 }
  26.                 char d = s[left];//d是将移出窗口的字符
  27.                 left++;//左移窗口
  28.                  //进行窗口内一系列数据的更新
  29.                 if (need.count(d)) {
  30.                     if (window[d] == need[d])
  31.                         valid--;
  32.                     window[d]--;
  33.                 }
  34.             }
  35.         }
  36.         //返回最小覆盖字串
  37.         return len == INT_MAX ? "" : s.substr(start,len);
  38.     }
  39. };