1. 覆盖子串
子字符串: 是字符串中连续的 非空 字符序列
覆盖子串：和子序列的区别为，覆盖子串不要求顺序，即ADCB的子串有：ABC、ABD等, 而子序列有：ADC, ADB等
2. 思路
由于覆盖子串不再考虑顺序性，一般都会使用Map来记录字符和字符频次，以此来判断子串的合法性
3. 题目
3.1 最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
3.1.1 思路
暴力解法就是：
- 2个指针i，j去遍历s，取s[i-j]上的字符去和t对比O(n^2)
- 如果 s[i-j]中有t，那么记录最小长度
- 如果 s[i-j]中不包含t，直接跳过
- s[i-j]中 t 有没有，也是一个O(n)的时间复杂度
- 时间整体复杂度：O(n^3)
正常解法：遍历一次，滑动窗口 + 记忆化
- 使用map1记录t中每个字符出现的次数
- 使用windowMap记录，s上的窗口内 & 有t的目标字符出现的次数，在t中不存在的无效的字符不记录
- 遍历s，检查窗口内map是否覆盖t
- 如果符合，记录minLegth,minStartIndex，窗口缩小，left++，windowMap更新
- 如果不符合，扩窗口，right++
- 最后返回: s.substring(minStartIndex, minStartIndex + minLength) 即可
时间复杂度： 由于遍历O(n)，检查窗口内map是否覆盖t也是O(n)，整体O(n^2)
public String minWindow(String s, String t) {
//记录t中字符出现的次数
Map<Character, Integer> map1 = new HashMap<>();
//动态窗口记录 有目标字符 以及 次数
Map<Character, Integer> windowMap = new HashMap<>();
int l = 0;
int r= 0;
int minLength = Integer.MAX_VALUE;
int minStartIndex = 0;
//构建map1
for (char c : t.toCharArray()) {
map1.put(c, map1.getOrDefault(c, 0) + 1);
}
char[] sArr = s.toCharArray();
while (r < s.length()){
char currentChar = sArr[r];
//有目标字符的才加入
if(map1.get(currentChar)!=null){
windowMap.put(currentChar, windowMap.getOrDefault(currentChar, 0)+1);
}
if(r - l + 1 < t.length()){
//窗口不够长度，扩，r++
r++;
continue;
}
//去检查
boolean check = checkWindow(windowMap, map1, t);
if(check){
if(r-l+1 < minLength){
minLength = r-l+1;
minStartIndex = l;
}
//尝试缩小,更新窗口统计
while (r - l + 1 > t.length()){
char tmpLeftChar = s.charAt(l);
//如果当前的字符在winds中，窗口缩小，对应的次数需要减1
if(map1.get(tmpLeftChar)!=null){
windowMap.put(tmpLeftChar, windowMap.get(tmpLeftChar)-1);
}
l++;
boolean checkWindow = checkWindow(windowMap, map1, t);
if(checkWindow){
if(r-l+1 < minLength){
minLength = r-l+1;
minStartIndex = l;
}
}else {
break;
}
}
r++;
}else {
//不符合，那么扩窗口，r++
r++;
}
}
return minLength == Integer.MAX_VALUE ? "" : s.substring(minStartIndex, minStartIndex + minLength);
}
private boolean checkWindow(Map<Character, Integer> windowMap, Map<Character, Integer> map1, String t){
for (char c : t.toCharArray()) {
Integer windowsExistCount = windowMap.get(c);
Integer count = map1.get(c);
if(windowsExistCount == null){
return false;
}
if(windowsExistCount < count){
return false;
}
}
return true;
}
3.1.2 优化解法
设t=ABC
优化解法：遍历一次，滑动窗口 + 记忆化 + 检查优化
- 使用map1记录t中每个字符出现的次数
- 使用windowMap记录，s上的窗口内 & 有t的目标字符出现的次数，在t中不存在的无效的字符不记录，同时使用windowCount，记录窗口最小有效字符数，不会重复加入，即窗口[ABBC]，那么windowCount=3，而不是4
- 遍历s，检查窗口内map是否覆盖t（判断windowsCount>=map1.size()即可）
- 如果符合，记录minLegth,minStartIndex，窗口缩小，left++，windowMap更新
- 如果不符合，扩窗口，right++
- 最后返回: s.substring(minStartIndex, minStartIndex + minLength) 即可
时间复杂度： 遍历O(n)
代码如下：
public String minWindowUpgrade(String s, String t) {
//记录t中字符出现的次数
Map<Character, Integer> map1 = new HashMap<>();
//动态窗口记录 有目标字符 以及 次数
Map<Character, Integer> windowMap = new HashMap<>();
int l = 0;
int r= 0;
int minLength = Integer.MAX_VALUE;
int minStartIndex = 0;
int wincount=0;
//构建map1
for (char c : t.toCharArray()) {
map1.put(c, map1.getOrDefault(c, 0) + 1);
}
char[] sArr = s.toCharArray();
while (r < s.length()){
char currentChar = sArr[r];
//有目标字符的才加入
if(map1.get(currentChar)!=null){
windowMap.put(currentChar, windowMap.getOrDefault(currentChar, 0)+1);
if(map1.get(currentChar).intValue() == windowMap.get(currentChar)){
wincount++;
}
}
if(r - l + 1 < t.length()){
//窗口不够长度，扩，r++
r++;
continue;
}
//去检查
boolean check = checkWindowUpgrade(wincount, map1.size());
if(check){
if(r-l+1 < minLength){
minLength = r-l+1;
minStartIndex = l;
}
//尝试缩小,更新窗口统计
while (wincount == map1.size()){
char tmpLeftChar = s.charAt(l);
//如果当前的字符在winds中，窗口缩小，对应的次数需要减1
if(map1.get(tmpLeftChar)!=null){
if(map1.get(tmpLeftChar).intValue() == windowMap.get(tmpLeftChar)){
wincount--;
}
windowMap.put(tmpLeftChar, windowMap.get(tmpLeftChar)-1);
}
l++;
boolean checkWindow = checkWindowUpgrade(wincount, map1.size());
if(checkWindow){
if(r-l+1 < minLength){
minLength = r-l+1;
minStartIndex = l;
}
}else {
break;
}
}
r++;
}else {
//不符合，那么扩窗口，r++
r++;
}
}
return minLength == Integer.MAX_VALUE ? "" : s.substring(minStartIndex, minStartIndex + minLength);
}
private boolean checkWindowUpgrade(int windowsCount, int tCount){
return windowsCount>=tCount;
}
