题目描述

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

注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-window-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

样例

示例 1：

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

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

算法1

(滑动窗口)

例如t= abc
创建一个t 的hash表储存t的每个字符的个数，遍历str，递减每一个字符，当hash中有为0的字符时，说明已经在str中找到一个合适的字符了，c。当c满足后，即可根据str是否最小长度更新答案。
当c满足后，即找到所有的字符，继续遍历str，此时如果又找到t中字符，继续递减，当hash[j] < 0时，说明此时i-j中已经有多余的字符了，此时移动j j，移除当前多余的字符，并且hash[j]++.

时间复杂度

参考文献 https://www.acwing.com/activity/content/discuss/12/1/ 抄的，只是添加个注释

C++ 代码

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> hash;
        int cnt = 0;
        for (auto c : t)
        {
            if (!hash[c]) cnt ++ ;
            hash[c] ++ ;
        }//创建一个t 的hash表储存t的每个字符的个数

        string res = "";
        for (int i = 0, j = 0, c = 0; i < s.size(); i ++ ) //，遍历str，
        {
            if (hash[s[i]] == 1) c ++ ;  //当hash中有为0的字符时，说明已经在str中找到一个合适的字符了，c++。
            hash[s[i]] -- ; //遍历str，递减每一个字符
            while (c == cnt && hash[s[j]] < 0) hash[s[j ++ ]] ++ ; //当c满足后，即找到所有的字符，继续遍历str，此时如果又找到t中字符，继续递减，
            //当hash[j] < 0时，说明此时i-j中已经有多余的字符了，此时移动j ++j，移除当前多余的字符，并且hash[j]++.
            if (c == cnt)//当c满足后，即可根据str是否最小长度更新答案。
            {
                if (res.empty() || res.size() > i - j + 1) res = s.substr(j, i - j + 1);
            }
        }

        return res;
    }
};

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla