题解 | #最小覆盖子串#

题目主要信息：

• 在S字符串中找到包含T字符串所有字符的最小连续子串
• 两个字符串仅包含大小写字母
• 如果S中没有包含T中所有字符的子串，返回空字符串""，若有，则存在唯一最短

举一反三：

学习完本题的思路你可以解决如下题目：

BM92. 最长无重复数组

方法：哈希表匹配（推荐使用）

知识点1：滑动窗口

滑动窗口是指在数组、字符串、链表等线性结构上的一段，类似一个窗口，而这个窗口可以依次在上述线性结构上从头到尾滑动，且窗口的首尾可以收缩。我们在处理滑动窗口的时候，常用双指针来解决，左指针维护窗口左界，右指针维护窗口右界，二者同方向不同速率移动维持窗口。

知识点2：哈希表

哈希表是一种根据关键码（key）直接访问值（value）的一种数据结构。而这种直接访问意味着只要知道key就能在$O(1)O(1)$时间内得到value，因此哈希表常用来统计频率、快速检验某个元素是否出现过等。

思路：

字符串仅包含大小写字母，则字符集是已知且有限的，那这种情况下我们可以考虑快速查找某个元素是否出现过的哈希表——只需要维护一个哈希表，将字符串T中的字符作为key值，初始化时当字符在T中出现一次则对应的value值减1：

for(int i = 0; i < T.length(); i++)
    //初始化哈希表都为负数，找的时候再加为正
    hash[T.charAt(i)] -= 1; 

后续如果在字符串S中找到相应字符就可以将其加回来:

char c = S.charAt(fast);
//目标字符匹配+1
hash[c]++;

然后使用双指针维护滑动窗口，在窗口内，哈希表中value都大于0：

for (int i = 0; i < hash.length; i++) {
    if (hash[i] < 0)
        return false;
}
return true;

这个窗口内出现了T中所有的字符串，此时可以尝试缩小窗口，因为双指针同步向右遍历，因此缩小窗口只能是缩小左界。

具体做法：

• step 1：建立哈希表，遍历字符串T，统计各个字符出现的频率，频率计为负数。
• step 2：依次遍历字符串S，如果匹配则将哈希表中的相应的字符加1。
• step 3：在遍历过程中维护一个窗口，如果哈希表中所有元素都大于0，意味着已经找全了，则窗口收缩向左移动，找最小的窗口，如果不满足这个条件则窗口右移继续匹配。窗口移动的时候需要更新最小窗口，以取得最短子串。
• step 4：如果匹配到最后，窗口left（初始为-1）也没有右移，说明没有找到，返回空串即可。
• step 5：最后使用字符串截取函数，截取刚刚记录下的窗口即可得到符合条件的最短子串。

图示：

Java代码实现：

import java.util.*;
public class Solution {
    //检查是否有小于0的
    boolean check(int[] hash) { 
        for (int i = 0; i < hash.length; i++) {
            if (hash[i] < 0)
                return false;
        }
        return true;
    };
    
    public String minWindow (String S, String T) {
        int cnt = S.length() + 1;
        //记录目标字符串T的字符个数
        int[] hash = new int[128]; 
        for(int i = 0; i < T.length(); i++)
        //初始化哈希表都为负数，找的时候再加为正
            hash[T.charAt(i)] -= 1; 
        int slow = 0, fast = 0;  
        //记录左右区间
        int left = -1, right = -1;  
        for(; fast < S.length(); fast++){
            char c = S.charAt(fast);
            //目标字符匹配+1
            hash[c]++;
            //没有小于0的说明都覆盖了，缩小窗口
            while(check(hash)){  
                //取最优解
                if(cnt > fast - slow + 1){ 
                    cnt = fast - slow + 1;  
                    left = slow;
                    right = fast;
                }
                c = S.charAt(slow);
                //缩小窗口的时候减1
                hash[c]--; 
                //窗口缩小
                slow++;      
            }
        }
        //找不到的情况
        if(left == -1)     
            return "";
        return S.substring(left, right + 1);
    }
}

C++代码实现：

class Solution {
public:
    //检查是否有小于0的
    bool check(unordered_map<char, int> &hash) { 
        for (auto iter = hash.begin(); iter != hash.end(); iter++) {
            if (iter->second < 0)
                return false;
        }
        return true;
    }
    string minWindow(string S, string T) {
        int cnt = S.length() + 1;
        //记录目标字符串T的字符个数
        unordered_map<char, int> hash; 
        for(int i = 0; i < T.length(); i++)
            //初始化哈希表都为负数，找的时候再加为正
            hash[T[i]] -= 1; 
        int slow = 0, fast = 0;  
        //记录左右区间
        int left = -1, right = -1;  
        for(; fast < S.length(); fast++){
            char c = S[fast];
            //目标字符匹配+1
            if(hash.count(c))    
            hash[c]++;
            //没有小于0的说明都覆盖了，缩小窗口
            while(check(hash)){   
                //取最优解
                if(cnt > fast - slow + 1){ 
                    cnt = fast - slow + 1;  
                    left = slow;
                    right = fast;
                }
                char c = S[slow];
                if(hash.count(c))
                    //缩小窗口的时候减1
                    hash[c]--; 
                //窗口缩小
                slow++;      
          }
      }
      //找不到的情况
      if (left == -1)     
          return "";
      return string(S.begin() + left, S.begin() + (right + 1));
  }
};

Python实现代码：

class Solution:
    #检查是否有小于0的
    def check(self, hash:dict()): 
        for key, value in hash.items():
            if value < 0:
                return False
        return True

    def minWindow(self , S: str, T: str) -> str:
        cnt = len(S) + 1
        #记录目标字符串T的字符个数
        hash = dict() 
        for i in range(len(T)):
            if T[i] in hash:
                #初始化哈希表都为负数，找的时候再加为正
                hash[T[i]] -= 1 
            else:
                hash[T[i]] = -1
        slow = 0
        fast = 0
        left = -1
        #记录左右区间
        right = -1 
        while fast < len(S):
            c = S[fast]
            #目标字符匹配+1
            if c in hash:
                hash[c] += 1
            #没有小于0的说明都覆盖了，缩小窗口
            while (Solution.check(self, hash)) :   
                #取最优解
                if  cnt > fast - slow + 1: 
                    cnt = fast - slow + 1
                    left = slow
                    right = fast
                c = S[slow]
                if c in hash:
                    #缩小窗口的时候减1
                    hash[c] -= 1 
                #窗口缩小
                slow += 1      
            fast += 1
        #找不到的情况
        if left == -1:    
            return ""
        return S[left:right+1]

复杂度分析：

• 时间复杂度：$O(C\ast n_S+n_T)O(C*n\_S+n\_T)$，其中C为T字符串的字符集大小，本题中为52个字母，$n_{S}n\_S$为字符串S的长度，$n_{T}n\_T$为字符串T的长度
• 空间复杂度：$O(C)O(C)$，哈希表长度不会超过字符串T的字符集大小