友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
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由英文字母组成
进阶：你能设计一个在 O(m+n) 时间内解决此问题的算法吗？
思路分析
滑动窗口
-
一刷
-
二刷
-
三刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
* Runtime: 489 ms, faster than 5.03% of Java online submissions for Minimum Window Substring.
* Memory Usage: 322.8 MB, less than 5.32% of Java online submissions for Minimum Window Substring.
*
* ↓ 优化：在最后输出时，才截取字符串。
*
* Runtime: 33 ms, faster than 16.02% of Java online submissions for Minimum Window Substring.
* Memory Usage: 44.4 MB, less than 5.32% of Java online submissions for Minimum Window Substring.
*/
public String minWindow(String s, String t) {
if (Objects.isNull(s) || s.length() == 0
|| Objects.isNull(t) || t.length() == 0
|| s.length() < t.length()) {
return "";
}
Map<Character, Integer> needs = new HashMap<>(t.length());
for (char c : t.toCharArray()) {
needs.put(c, needs.getOrDefault(c, 0) + 1);
}
int left = 0, right = 0;
int minLength = Integer.MAX_VALUE;
int start = 0;
int match = 0;
Map<Character, Integer> windows = new HashMap<>(t.length());
while (right < s.length()) {
char rChar = s.charAt(right);
if (needs.containsKey(rChar)) {
int rCount = windows.getOrDefault(rChar, 0) + 1;
windows.put(rChar, rCount);
if (rCount == needs.get(rChar)) {
match++;
}
}
right++;
while (match == needs.size()) {
if (right - left < minLength) {
minLength = right - left;
start = left;
}
char lChar = s.charAt(left);
if (needs.containsKey(lChar)) {
int lCount = windows.get(lChar) - 1;
windows.put(lChar, lCount);
if (lCount < needs.get(lChar)) {
match--;
}
}
left++;
}
}
return minLength == Integer.MAX_VALUE ? "" : s.substring(start, start + minLength);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/**
* 自己实现失败后，参考社区答案修改的
*
* @author D瓜哥 · https://www.diguage.com
* @since 2024-07-02 17:03:23
*/
public String minWindow(String s, String t) {
if (s == null || s.isEmpty() || t == null || t.isEmpty() || s.length() < t.length()) {
return "";
}
// 初始化 need，记录 t 中每个字符的出现次数
char[] chars = s.toCharArray();
Map<Character, Integer> need = new HashMap<>();
for (char c : t.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) + 1);
}
Map<Character, Integer> window = new HashMap<>();
int left = 0, right = 0; // 窗口的左右边界
int valid = 0; // 已经匹配上的字符数量
int start = 0, minLen = Integer.MAX_VALUE; // 最小窗口的起始位置和长度
while (right < s.length()) {
// 扩大窗口
char rc = chars[right];
right++;
// 更新窗口内字符的计数
if (need.containsKey(rc)) {
window.put(rc, window.getOrDefault(rc, 0) + 1);
if (window.get(rc).equals(need.get(rc))) {
valid++;
}
}
// 收缩窗口
while (need.size() == valid) {
// 更新最小窗口的起始位置和长度
if (right - left < minLen) {
start = left;
minLen = right - left;
}
char lc = chars[left];
// 缩小窗口，移动左边界
if (need.containsKey(lc)) {
window.put(lc, window.get(lc) - 1);
if (window.get(lc) < need.get(lc)) {
valid--;
}
}
left++;
}
}
return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-03-21 11:08:35
*/
public String minWindow(String s, String t) {
if (s == null || t == null || s.isEmpty() || t.isEmpty() || s.length() < t.length()) {
return "";
}
Map<Character, Integer> target = new HashMap<>();
for (char c : t.toCharArray()) {
target.put(c, target.getOrDefault(c, 0) + 1);
}
int left = 0, right = 0;
int valid = 0, startIdx = 0, minLength = Integer.MAX_VALUE;
Map<Character, Integer> windows = new HashMap<>();
while (right < s.length()) {
char rc = s.charAt(right);
right++;
windows.put(rc, windows.getOrDefault(rc, 0) + 1);
if (target.containsKey(rc)
&& Objects.equals(target.get(rc), windows.get(rc))) {
valid++;
}
while (valid == target.size()) {
if (right - left < minLength) {
minLength = right - left;
startIdx = left;
}
char lc = s.charAt(left);
windows.put(lc, windows.getOrDefault(lc, 0) - 1);
if (target.containsKey(lc) && windows.get(lc) < target.get(lc)) {
valid--;
}
left++;
}
}
return minLength == Integer.MAX_VALUE ? "" : s.substring(startIdx, startIdx + minLength);
}