题目链接

LeetCode

题目描述

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

注意：

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

示例 1：

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

示例 2：

输入： s = “a”, t = “a”
输出： “a”

示例 3:

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

提示：

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

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

解题思路

方法一：滑动窗口

我们可以用滑动窗口的思想解决这个问题。在滑动窗口类型的问题中都会有两个指针，一个用于「延伸」现有窗口的 r 指针，和一个用于「收缩」窗口的 l 指针。在任意时刻，只有一个指针运动，而另一个保持静止。
我们在 s 上滑动窗口，通过移动 r 指针不断扩张窗口。当窗口包含 t 全部所需的字符后，如果能收缩，我们就收缩窗口直到得到最小窗口。
76. 最小覆盖子串** - 图1
如何判断当前的窗口包含所有 t 所需的字符呢？我们可以用一个哈希表表示 t 中所有的字符以及它们的个数，用一个哈希表动态维护窗口中所有的字符以及它们的个数，如果这个动态表中包含 t 的哈希表中的所有字符，并且对应的个数都不小于 t 的哈希表中各个字符的个数，那么当前的窗口是「可行」的。

class Solution {
public:
    string minWindow(string s, string t) {
        int len1 = s.length();
        int len2 = t.length();
        if(len1==0||len2==0||len1<len2){
            return "";
        }
        int minLen = INT_MAX;
        int left = 0;
        int right = 0;
        int distance = 0;
        int begin = 0;
        for(const char& c : t){
            tFreq[c]++;
        }
        while(right<len1){
            if(tFreq[s[right]]==0){
                right++;
                continue;
            }
            if(winFreq[s[right]]<tFreq[s[right]]){
                distance++;
            }
            winFreq[s[right]]++;
            right++;
            while(distance==len2){
                if(right-left < minLen){
                    minLen = right - left;
                    begin = left;
                }
                if(tFreq[s[left]]==0){
                    left++;
                    continue;
                }
                if(winFreq[s[left]] == tFreq[s[left]]){
                    distance--;
                }
                winFreq[s[left]]--;
                left++;
            }
        }
        if(minLen == INT_MAX){
            return "";
        }
        return s.substr(begin,minLen);
    }
private:
    unordered_map<char,int> winFreq;
    unordered_map<char,int> tFreq;
};

public class Solution {
    public String minWindow(String s, String t) {
        int sLen = s.length();
        int tLen = t.length();
        if(sLen==0||tLen==0||sLen<tLen){
            return "";
        }
        char[] charArrayS = s.toCharArray();
        char[] charArrayT = t.toCharArray();
        int[] winFreq = new int[128];
        int[] tFreq = new int[128];
        for (char c : charArrayT){
            tFreq[c]++;
        }
        int distance = 0;
        int minLen = Integer.MAX_VALUE;
        int begin = 0;
        int left = 0;
        int right = 0;
        while(right<sLen){
            // 如果t中没有当前元素，跳过
            if (tFreq[charArrayS[right]]==0){
                right++;
                continue;
            }
            // 如果当前窗口中当前元素的个数小于t中的个数，distance加一
            if(winFreq[charArrayS[right]] < tFreq[charArrayS[right]]){
                distance++;
            }
            winFreq[charArrayS[right]]++;
            right++;
            // 窗口中包含t中所有的元素
            while (distance == tLen){
                if (right-left < minLen){
                    minLen = right - left;
                    begin = left;
                }
                if (tFreq[charArrayS[left]]==0){
                    left++;
                    continue;
                }
                if(winFreq[charArrayS[left]] == tFreq[charArrayS[left]]){
                    distance--;
                }
                winFreq[charArrayS[left]]--;
                left++;
            }
        }
        if (minLen == Integer.MAX_VALUE){
            return "";
        }
        return s.substring(begin,begin+minLen);
    }
}

class Solution {
    Map<Character, Integer> oriMap = new HashMap<>();
    Map<Character, Integer> cntMap = new HashMap<>();
    public String minWindow(String s, String t) {
        for(int i = 0; i < t.length(); ++i){
            oriMap.put(t.charAt(i) , oriMap.getOrDefault(t.charAt(i), 0) + 1);
        }
        int len = Integer.MAX_VALUE;
        int L = 0, R = 0;
        int ansL = 0, ansR = 0;
        while(R < s.length()){
            // 如果当前字符属于t,
            if(R < s.length() && oriMap.containsKey(s.charAt(R))){
                cntMap.put(s.charAt(R) , cntMap.getOrDefault(s.charAt(R), 0) + 1);
            }
            // 左指针右移
            while(check() && L <= R){
                if(R - L + 1 <len){
                    len = R - L + 1;
                    ansL = L;
                    ansR = L + len;
                }
                if(oriMap.containsKey(s.charAt(L))){
                    cntMap.put(s.charAt(L) , cntMap.getOrDefault(s.charAt(L), 0) - 1);
                }
                ++L;
            }
            ++R;
        }
        return ansR == 0 ? "" : s.substring(ansL, ansR);
    }
    private boolean check(){
        for(Map.Entry<Character, Integer> entry : oriMap.entrySet()){
            if(cntMap.getOrDefault(entry.getKey(), 0) < entry.getValue()){
                return false;
            }
        }
        return true;
    }
}

时间复杂度 O(C⋅∣s∣+∣t∣) 最坏情况下左右指针对 s 的每个元素各遍历一遍，哈希表中对 s 中的每个元素各插入、删除一次，对 t 中的元素各插入一次。每次检查是否可行会遍历整个 t 的哈希表，哈希表的大小与字符集的大小有关，设字符集大小为 C，则渐进时间复杂度为 O(C⋅∣s∣+∣t∣)。
空间复杂度 O(C)：这里用了两张哈希表作为辅助空间，每张哈希表最多不会存放超过字符集大小的键值对，我们设字符集大小为 C ，则渐进空间复杂度为 O(C)。