最小覆盖子串
- 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。
- 如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
注意：
- 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
- 如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 1：
- 输入：s = “ADOBECODEBANC”, t = “ABC”
- 输出：“BANC”
- 解释：最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、‘B’ 和 ‘C’。
解题思路
- 1、使用滑动窗口和哈希表的方法来解决问题。
- 2、首先，构建目标字符串 t 的字符频率统计targetMap。
- 3、然后，使用两个指针 left 和 right 表示滑动窗口的左右边界，初始时都指向字符串 s 的开头。
- 4、在遍历字符串 s 的过程中，维护一个哈希表 windowMap 用于记录窗口内字符的频率统计。
- 5、移动 right 指针，直到窗口包含了字符串 t 的所有字符（windowMap 中的字符频率统计与目标字符串 t 的字符频率统计相同）。
- 6、当窗口内包含了目标字符串所有字符时，尝试移动左指针缩小窗口，同时更新最小覆盖子串的起始位置和长度。
- 7、在遍历过程中，记录下最小窗口的起始索引和长度。
- 8、返回最小窗口的子串。
java实现
public class MinWindowSubstring {
public String minWindow(String s, String t) {
if (s == null || t == null || s.length() == 0 || t.length() == 0) {
return "";
}
// 使用两个哈希表分别存储目标字符串t和滑动窗口内的字符频次
Map<Character, Integer> targetMap = new HashMap<>();
Map<Character, Integer> windowMap = new HashMap<>();
// 初始化目标字符串t的字符频次表
for (char c : t.toCharArray()) {
targetMap.put(c, targetMap.getOrDefault(c, 0) + 1);
}
// 使用两个指针定义滑动窗口
int left = 0;
int right = 0;
// 记录最小覆盖子串的起始位置和长度
int minStart = 0;
int minLength = Integer.MAX_VALUE;
// 记录滑动窗口内已经匹配的字符数量
int matchedChars = 0;
while (right < s.length()) {
// 右指针向右移动，更新滑动窗口内字符频次表
char rightChar = s.charAt(right);
windowMap.put(rightChar, windowMap.getOrDefault(rightChar, 0) + 1);
// 如果右指针所指的字符在目标字符串t中，并且滑动窗口内该字符的数量达到目标字符的数量，matchedChars加1
if (targetMap.containsKey(rightChar)
&& windowMap.get(rightChar).equals(targetMap.get(rightChar))) {
matchedChars++;
}
// 当滑动窗口内已经匹配了目标字符串t中的所有字符时，尝试缩小窗口
while (matchedChars == targetMap.size()) {
// 更新最小覆盖子串的起始位置和长度
if (right - left + 1 < minLength) {
minLength = right - left + 1;
minStart = left;
}
// 左指针向右移动，更新滑动窗口内字符频次表
char leftChar = s.charAt(left);
windowMap.put(leftChar, windowMap.get(leftChar) - 1);
// 如果左指针所指的字符在目标字符串t中，并且滑动窗口内该字符的数量小于目标字符的数量，matchedChars减1
if (targetMap.containsKey(leftChar)
&& windowMap.get(leftChar) < targetMap.get(leftChar)) {
matchedChars--;
}
// 缩小窗口
left++;
}
// 右指针向右移动，扩大窗口
right++;
}
// 如果找到了最小覆盖子串，则返回该子串，否则返回空字符串
return minLength == Integer.MAX_VALUE ? ""
: s.substring(minStart, minStart + minLength);
}
public static void main(String[] args) {
MinWindowSubstring solution = new MinWindowSubstring();
String s = "ADOBECODEBANC";
String t = "ABC";
String result = solution.minWindow(s, t);
System.out.println(result); // 输出："BANC"
}
}
时间空间复杂度
- 时间复杂度：O(n)，其中 n 是字符串 s 的长度
- 空间复杂度：O(m)，其中 m 是字符串 t 的长度
