原题地址: . - 力扣（LeetCode）
给你一个字符串 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 的子串中， 因此没有符合条件的子字符串，返回空字符串。
暴力法
暴力法就是遍历所有子串，然后统计子串中每个字符出现的次数，然后跟t中每个字符出现的次数做比较，如果包含t中所有字符并且字符出现的次数大于等于t,则说明该子串符合条件，找出所有满足条件的子串，通过比较得到最小子串
public String minWindow(String s, String t) {
// 保存自小子串
String result = "";
// 统计t中字符串数量
Map<Character, Integer> tCharStatis = statis(t);
// 遍历s
for (int i = 0; i < s.length(); i++) {
// 遍历子串,子串范围为[i,j)
for (int j = i + t.length(); j <= s.length(); j++) {
String subStr = s.substring(i, j);
Map<Character, Integer> subCharStatis = statis(subStr);
// 如果子串包含t,则判断是否为最小子串
if (check(subCharStatis, tCharStatis)) {
if ("".equals(result) || subStr.length() < result.length()) {
result = subStr;
}
}
}
}
return result;
}
// 统计字符串中单个字符数量
private Map<Character, Integer> statis(String str) {
Map<Character, Integer> map = new HashMap<>();
for (int i = 0; i < str.length(); i++) {
int count = map.getOrDefault(str.charAt(i), 0);
count++;
map.put(str.charAt(i), count);
}
return map;
}
// 判断子串是否包含t
private boolean check(Map<Character, Integer> subStatis, Map<Character, Integer> tStatis) {
for (Character c : tStatis.keySet()) {
int subCount = subStatis.getOrDefault(c, 0);
if (subCount < tStatis.get(c)) return false;
}
return true;
}
效果:
代码没问题，但是时间复杂度太高，没法满足需求
滑动窗口
暴力法的缺点是显而易见的：时间复杂度过大，超出了运行时间限制。在哪些方面可以优化呢？
仔细观察可以发现，我们在暴力求解的时候，做了很多无用的比对：对于字符串“ADOBECODEBANC”，当找到一个符合条件的子串“ADOBEC”后，我们会继续仍以“A”作为起点扩展这个子串，得到一个符合条件的“ADOBECO”——它肯定符合条件，也肯定比之前的子串长，这其实是完全不必要的。
代码实现上，我们可以定义两个指针：指向子串“起始点”的左指针，和指向子串“结束点”的右指针。它们一个固定、另一个移动，彼此交替向右移动，就好像开了一个大小可变的窗口、在不停向右滑动一样，所以这就是非常经典的滑动窗口解决问题的应用场景。所以有时候，滑动窗口也可以归类到双指针法。
public String minWindow1(String s, String t) {
// 保存自小子串
String result = "";
// 统计t中字符串数量
Map<Character, Integer> tCharStatis = statis(t);
int lp = 0;
int rp = t.length();
while (rp <= s.length()) {
String subStr = s.substring(lp, rp);
Map<Character, Integer> subCharStatis = statis(subStr);
// 子串符合条件，则左指针右移
if (check(subCharStatis, tCharStatis)) {
if ("".equals(result) || subStr.length() < result.length()) {
result = subStr;
}
lp++;
} else {
//不符合条件则右指针右移继续寻找
rp++;
}
}
return result;
}
// 统计字符串中单个字符数量
private Map<Character, Integer> statis(String str) {
Map<Character, Integer> map = new HashMap<>();
for (int i = 0; i < str.length(); i++) {
int count = map.getOrDefault(str.charAt(i), 0);
count++;
map.put(str.charAt(i), count);
}
return map;
}
// 判断子串是否包含t
private boolean check(Map<Character, Integer> subStatis, Map<Character, Integer> tStatis) {
for (Character c : tStatis.keySet()) {
int subCount = subStatis.getOrDefault(c, 0);
if (subCount < tStatis.get(c)) return false;
}
return true;
}
效果:
比之前有进步，但是还需进一步优化
滑动窗口优化
我们判断S是否满足包含T中所有字符的时候，调用的方法check其实又是一个暴力法：遍历T中所有字符频次，一一比对。上面的复杂度分析也可以看出，遍历s只用了线性时间，但每次都要遍历一遍T的频次哈希表，这就耗费了大量时间。
我们已经知道，每次指针的移动，只涉及到一个字符的增减。所以我们其实不需要知道完整的频次HashMap，只要获取改变的这个字符的频次，然后再和T中的频次比较，就可以知道新子串是否符合要求了。
public String minWindow(String s, String t) {
// 保存最小子串
String result = "";
// 统计t中字符串数量
Map<Character, Integer> tCharStatis = statis(t);
Map<Character, Integer> subCharStatis = new HashMap<>();
int lp = 0;
int rp = 1;
while (rp <= s.length()) {
char newChar = s.charAt(rp - 1);
// t中包含该字符再统计
if (tCharStatis.containsKey(newChar)) {
int count = subCharStatis.getOrDefault(newChar, 0);
subCharStatis.put(newChar, count + 1);
}
// 子串符合条件，则左指针右移
while (check(subCharStatis, tCharStatis) && lp < rp) {
if ("".equals(result) || rp - lp < result.length()) {
result = s.substring(lp, rp);
}
char removedChar = s.charAt(lp);
if (tCharStatis.containsKey(removedChar)) {
subCharStatis.put(removedChar, subCharStatis.getOrDefault(removedChar, 0) - 1);
}
lp++;
}
rp++;
}
return result;
}
// 统计字符串中单个字符数量
private Map<Character, Integer> statis(String str) {
Map<Character, Integer> map = new HashMap<>();
for (int i = 0; i < str.length(); i++) {
int count = map.getOrDefault(str.charAt(i), 0);
count++;
map.put(str.charAt(i), count);
}
return map;
}
// 判断子串是否包含t
private boolean check(Map<Character, Integer> subStatis, Map<Character, Integer> tStatis) {
for (Character c : tStatis.keySet()) {
int subCount = subStatis.getOrDefault(c, 0);
if (subCount < tStatis.get(c)) return false;
}
return true;
}
