题目描述

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

注意：

对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例

示例一

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

示例二

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

示例三

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

解题思路

这时一道非常经典的滑动窗口题目，所以我们可以采用双指针+双窗口的解法。假设现在两个字符串的状态如下：

我们新建两个窗口window和need。其中need窗口用于记录每个记录需要匹配几次；window窗口则用于记录当前滑动窗口期中每个字符出现的次数，所以这两个变量我们都可以用unordered_map。此时，我们建立滑动窗口，让left和right都指向字符串S的起始。

此时我们把right指针往右移一步，此时字符A就被添加到了Window窗口之中。

之后，我们不断迭代这个过程，直到我们Window窗口中的字符出现满足need窗口中每个字符出现的个数。

这个时候我们就拿到第一个匹配的子串"ADOBEC"，我们可以开始尝试收缩左边界了，一直收缩到Window窗口不满足need窗口。

收缩完之后，我们继续刚刚找子串的过程，这个时候我们会找到第二个 “满足条件” 的子串。

可以看到这个子串有点多余，所以我们收缩左边界，得到第二个满足条件的子串"CODEBA"
之后再次迭代，直到终止条件right出字符串S的边界，最后比对我们找到满足条件的子串中长度的最小值就可以了。这个案例中是"BANC"。

代码呈现

class Solution {public:/*** @brief leetcode 提供的函数** @param s 被匹配的字符串* @param t 待匹配的字符串* @return string 最小覆盖子串*/string minWindow(string s, string t) {unordered_map<char, int> need;    //需要凑齐的子串unordered_map<char, int> window;  //窗口中的字符//记录待匹配的字符中每个字符出现的次数for (char c : t) {need[c]++;}int left = 0;   //左边界int right = 0;  //右边界int valid = 0;  //记录匹配上的字符数int str_start = 0;  // s字符串起始的位置int len = INT32_MAX;int s_size = s.size();while (right < s_size) {char ch = s[right];right++;if (need.count(ch)) {window[ch]++;if (window[ch] == need[ch]) {//一个字符完全匹配上了valid++;}}//判断左侧窗口是否需要收缩while (valid == need.size()) {if (right - left < len) {str_start = left;len = right - left;}//移出字符char delete_ch = s[left];left++;if (need.count(delete_ch)) {if (window[delete_ch] == need[delete_ch]) {valid--;}window[delete_ch]--;}}}return len == INT32_MAX ? "" : s.substr(str_start, len);}
};

参考文献

[1] labuladong的算法小抄[M].付东来