力扣最热一百题——最小覆盖子串

题目链接：76. 最小覆盖子串 - 力扣（LeetCode）

题目描述

示例

提示：

解法一：滑动窗口

1. 初始化

2. 构建 mapT

3. 滑动窗口

4. checkT 方法

5. 返回结果

Java写法：

运行时间

C++写法：

相比于Java主要改动：

运行时间

时间复杂度和空间复杂度

解法一极限优化

优化说明

运行时间

总结

题目链接：76. 最小覆盖子串 - 力扣（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 的子串中，
因此没有符合条件的子字符串，返回空字符串。

提示：

m == s.length
n == t.length
1 <= m, n <= 10^5
s 和 t 由英文字母组成

解法一：滑动窗口

1. 初始化

使用两个 HashMap（mapS 和 mapT）来记录字符出现的次数。mapT 用于存储字符串 t 中每个字符的出现次数，而 mapS 用于在滑动窗口过程中动态地记录当前窗口内字符的出现次数。
初始化结果子串的起始位置 resStart 为 -1（表示还未找到符合条件的子串），和结果子串的长度 resLen 为 s 的长度加1（确保初始时，任何可能的子串长度都会比这个值小，从而能够更新）。

2. 构建 `mapT`

遍历字符串 t，统计每个字符的出现次数，并存储在 mapT 中。

3. 滑动窗口

使用两个指针 left 和 right 来表示当前滑动窗口的左右边界。
使用一个 while 循环来移动这两个指针，直到 right 指针超出字符串 s 的范围或当前窗口已经包含了 t 的所有字符（通过 checkT 方法检查）。
在循环内部，首先检查是否需要向右扩展窗口（即移动 right 指针）。如果当前窗口不包含 t 的所有字符（!checkT(mapS, mapT) 为真），则扩展窗口（即将 s.charAt(right) 加入到 mapS 中，并右移 right 指针）。
如果当前窗口已经包含了 t 的所有字符，则尝试通过左移 left 指针来缩小窗口，直到窗口不再包含 t 的所有字符为止。在每次缩小窗口的过程中，都检查并更新结果子串的起始位置和长度（如果当前窗口长度更小的话）。

4. `checkT` 方法

这个方法用于检查 mapS 是否包含了 mapT 中的所有字符，并且每个字符的出现次数都不少于 mapT 中对应字符的出现次数。
遍历 mapT 中的每个字符，检查其在 mapS 中的出现次数是否满足条件。如果有任何一个字符不满足条件，则返回 false；否则返回 true。

5. 返回结果

循环结束后，如果找到了符合条件的子串（即 resStart 不为 -1），则返回该子串；否则返回空字符串 ""，表示没有找到符合条件的子串。

Java写法：

class Solution {public String minWindow(String s, String t) {int lenS = s.length();Map<Character,Integer> mapS = new HashMap<>();Map<Character,Integer> mapT = new HashMap<>();int resStart = -1;int resLen = lenS + 1;// 将t中的元素使用map集合存储起来for (int i = 0; i < t.length(); i++) {mapT.put(t.charAt(i),mapT.getOrDefault(t.charAt(i),0) + 1);}int left = 0;int right = 0;while (right < lenS || checkT(mapS, mapT)){if (right > lenS || !checkT(mapS, mapT)){// 如果当前窗口没有包含的话就添加元素,并右移rightmapS.put(s.charAt(right), mapS.getOrDefault(s.charAt(right),0) + 1);right++;}else {// 如果当前窗口包含了的话,判断并更新结果的起始位置和长度if (resLen > (right - left)){resStart = left;resLen = right - left;}// 就删除元素，并右移leftmapS.put(s.charAt(left), mapS.get(s.charAt(left)) - 1);left++;}}if(resStart != -1){return s.substring(resStart, resStart + resLen);}return "";}/*** 检查mapS是否包含了mapT中的全部字符* @return*/private boolean checkT(Map<Character, Integer> mapS, Map<Character, Integer> mapT) {for (Character character : mapT.keySet()) {if (mapT.get(character) > mapS.getOrDefault(character, 0)){return false;}}return true;}
}

运行时间

520送给大家

C++写法：


class Solution {
public:std::string minWindow(std::string s, std::string t) {int lenS = s.length();int lenT = t.length();std::unordered_map<char, int> mapS;std::unordered_map<char, int> mapT;// 将t中的元素使用map集合存储起来for (char c : t) {mapT[c]++;}int resStart = -1;int resLen = lenS + 1;int left = 0, right = 0;int required = mapT.size(); // 需要的不同字符数量int formed = 0; // 当前窗口中满足条件的不同字符数量while (right < lenS) {// 添加右指针的字符char c = s[right];mapS[c]++;// 如果当前字符在t中并且频率达标，则形成一个满足条件的字符if (mapT.count(c) && mapS[c] == mapT[c]) {formed++;}// 当当前窗口中包含了所有t的字符时，尝试收缩左指针while (left <= right && formed == required) {c = s[left];// 更新最小子串的长度和位置if (resLen > (right - left + 1)) {resStart = left;resLen = right - left + 1;}// 移除左指针指向的字符，并更新窗口mapS[c]--;if (mapT.count(c) && mapS[c] < mapT[c]) {formed--;}left++;}right++;}// 如果没有找到符合条件的子串，则返回空字符串，否则返回最小子串return resStart != -1 ? s.substr(resStart, resLen) : "";}
};

相比于Java主要改动：

数据结构：Java 的 HashMap 改为 C++ 的 unordered_map。
字符串处理：Java 的字符串操作改为 C++ 的 string 方法，例如 s.substr。
类型和语法：调整了类型和语法，使其符合 C++ 规范。
字符计数：在删除字符时，如果计数为 0，使用 erase 方法删除该字符。
主循环条件：适当调整了 while 循环的条件，以确保在右指针达到字符串末尾时不会越界。

运行时间

时间复杂度和空间复杂度

解法一极限优化

我就只写Java了，脑子要炸掉了

优化说明

窗口逻辑简化：原代码在主循环中条件判断较复杂，优化后将扩展右指针和收缩左指针的逻辑分开，使代码结构更清晰。
减少 mapS 的使用：在添加和移除字符时，直接更新 mapS 的计数，而不是每次都调用 getOrDefault，提高了性能。
优化 formed 计数：通过使用 formed 变量来跟踪当前满足条件的字符数量，避免每次调用检查 checkT 方法，减少了不必要的遍历。
使用数组来存储结果：使用 int[] result 数组来存储最小长度和指针位置，使代码更简洁，易于理解。

class Solution {public String minWindow(String s, String t) {int lenS = s.length(), lenT = t.length();// 如果s的长度小于t的长度，则直接返回空字符串if (lenS < lenT) return "";// 创建mapT，存储t中每个字符的频率Map<Character, Integer> mapT = new HashMap<>();for (char c : t.toCharArray()) {mapT.put(c, mapT.getOrDefault(c, 0) + 1);}// 创建mapS，存储当前窗口s中每个字符的频率Map<Character, Integer> mapS = new HashMap<>();int left = 0, right = 0;int required = mapT.size(); // 需要的不同字符数量int formed = 0; // 当前窗口中满足条件的不同字符数量int[] result = {-1, 0, 0}; // result[0]: 最小长度, result[1]: 左指针位置, result[2]: 右指针位置// 扩展右指针，形成窗口while (right < lenS) {char c = s.charAt(right);mapS.put(c, mapS.getOrDefault(c, 0) + 1);// 如果当前字符在t中，并且频率达到要求，则形成一个满足条件的字符if (mapT.containsKey(c) && mapS.get(c).intValue() == mapT.get(c).intValue()) {formed++;}// 当当前窗口中包含了所有t的字符时，尝试收缩左指针while (left <= right && formed == required) {c = s.charAt(left);// 更新最小子串的长度和位置if (result[0] == -1 || right - left + 1 < result[0]) {result[0] = right - left + 1;result[1] = left;result[2] = right;}// 移除左指针指向的字符，并更新窗口mapS.put(c, mapS.get(c) - 1);// 如果移除后该字符不再满足条件，则减少formed计数if (mapT.containsKey(c) && mapS.get(c).intValue() < mapT.get(c).intValue()) {formed--;}left++;}right++;}// 如果没有找到符合条件的子串，则返回空字符串，否则返回最小子串return result[0] == -1 ? "" : s.substring(result[1], result[2] + 1);}
}