LeetCode 76. 最小覆盖子串 (滑动窗口, 双指针, 字符串问题
原题链接
困难
作者:
JustDoIt11
,
2023-12-13 13:47:32
,
所有人可见
,
阅读 74
滑动窗口模板以及非常棒的题解 !
https://leetcode.cn/problems/find-all-anagrams-in-a-string/solutions/9749/hua-dong-chuang-kou-tong-yong-si-xiang-jie-jue-zi-/?envType=study-plan-v2&envId=top-100-liked
package leetcode;
import java.util.HashMap;
import java.util.Map;
public class lec76 {
public static void main(String[] args) {
System.out.println(minWindow("aaaaaaaaaaaabbbbbcdd", "abcdd"));
}
public static String minWindow(String s, String t) {
Map<Character, Integer> need = new HashMap<>();
Map<Character, Integer> window = new HashMap<>();
// init
for (int i = 0; i < t.length(); i ++ ) need.put(t.charAt(i), need.getOrDefault(t.charAt(i), 0) + 1);
// end
int l = 0, r = 0;
int valid = 0;
int st = 0, len = Integer.MAX_VALUE;
while (r < s.length()) {
char x = s.charAt(r);
r ++ ;
// date update
if (need.containsKey(x)) {
window.put(x, window.getOrDefault(x, 0) + 1);
if (window.get(x).equals(need.get(x))) valid ++ ;
}
// debug
// System.out.println("window : " + "[" + l + ", " + r + ")");
// end
while (valid == need.size()) {
if (r - l < len) {
st = l;
len = r - l;
}
char d = s.charAt(l);
l ++ ;
if (need.containsKey(d)) {
if (window.get(d).equals(need.get(d))) valid -- ;
window.put(d, window.get(d) - 1);
}
}
}
if (len == Integer.MAX_VALUE) return "";
return s.substring(st, st + len);
}
}
//abbbbbcdd
//abbbbbcdd
//abbbbbcdd