76.给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 “” 。
注意:
对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串,我们保证它是唯一的答案。
示例 1:
输入:s = “ADOBECODEBANC”, t = “ABC”
输出:“BANC”
解释:最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、‘B’ 和 ‘C’。
示例 2:
输入:s = “a”, t = “a”
输出:“a”
解释:整个字符串 s 是最小覆盖子串。
示例 3:
输入: s = “a”, t = “aa”
输出: “”
解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中,
因此没有符合条件的子字符串,返回空字符串。
提示:
m == s.length
n == t.length
1 <= m, n <= 105
s 和 t 由英文字母组成
- 在某个数组/字符串的某个区间内找到符合条件的子序列/子串,我们很容易想到滑动窗口。滑动窗口的思想就是左右端都从起点开始,右端不断后移直到窗口满足题目条件,也就得到了一个「可行解」,这时我们开始移动左端点,在这个过程中能得到该区间中的「最优解」,直到窗口不满足条件,我们继续移动右端点直到窗口又符合条件…
- 为什么「最终解」不会被遗漏,因为当我们得到一个可行解时,「最终解」相对它有三种可能,可以自行画图理解:
- 完全处于该区间:那我们不断右移左端点(缩小窗口)就一定能得到它
- 部分位于该区间:当我们不断右移左端点时,由于「最终解」的右部分不在该区间,也就表示当左端点至多缩小到最终答案左端点时,此时的区间就不再符合条件,左端点将停止右移,开始移动右端点,直到新的区间包含了「最终解」
- 完全不在该区间:那当我们继续滑动窗口的过程中一定会遇到以上两种情况
- 该题的滑动窗口解法的伪代码我们暂定如下
public String minWindow(String s, String t) { String res = ""; int left=0,right=0; while(left<=right){ while(窗口满足条件){ res = 处理结果; left++; } right++; } return res; }
- 难就难在当前窗口是否满足条件的判断,我们用变量 threshold 存储目标字符种类数,例如
aabbc
包含字符a,b,c
,threshold 此时为 3;我们用 hashMap 存储每种目标字符各自所需的数目,最后用 cur 表示当前满足所需个数的字符种类数,如果每种字符的所需个数都满足就表示窗口符合条件了,进行处理,只要有任意一种字符个数不足就结束窗口的缩小,继续移动右端点扩大窗口 int max = Integer.MAX_VALUE; public String minWindow(String s, String t) { String res = ""; // 最终结果的长度 int min = max; int left=0,right=0; // threshold:目标字符的种类数 // cur:当前窗口含有足够数目的目标字符的种类数 int threshold=0,cur=0; // 存储各个目标字符所需数量 Map<Character,Integer> map = new HashMap<>(); // 记录目标字符所需的种类和数量 for(char c:t.toCharArray()){ int n = map.getOrDefault(c,0); // 目标字符种类加一 if(n==0)++threshold; map.put(c, n+1); } while(right<s.length()){ char c = s.charAt(right); // 当前还需要的目标字符的数量 int n = map.getOrDefault(c,max); // c 不属于目标字符之一 if(n==max){ ++right; continue; } // c 属于目标字符且当前窗口已有足够数量的字符 c // 满足的种类数就加 1 if(--n==0)++cur; map.put(c,n); // 当前满足个数的目标字符的种类数 cur 为全部的目标字符种类数 threshold // 此时就表示窗口形成 while(cur==threshold && left<=right){ // 找到更优解就更新 if(right-left+1<min){ min = right-left+1; res = s.substring(left,right+1); } // 窗口左移(移除左端点对应字符 leftC) char leftC = s.charAt(left++); int leftN = map.getOrDefault(leftC,max); if(leftN==max)continue; // leftC 为目标字符且移除后所需数量将大于 0 // 那么移除该字符后满足个数的目标字符的种类数将减 1 if(++leftN>0)--cur; map.put(leftC,leftN); } ++right; } return res; }