题目
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 “” 。
注意:
对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串,我们保证它是唯一的答案。
示例 1:
输入:s = “ADOBECODEBANC”, t = “ABC”
输出:“BANC”
解释:最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、‘B’ 和 ‘C’。
解
class Solution {public String minWindow(String s, String t) {if (s.length() < t.length()) {return "";}Map<Character, Integer> map = new HashMap<>();for (int i = 0; i < t.length(); i++) {char ch = t.charAt(i);map.put(ch, map.getOrDefault(ch, 0) + 1);}int n = s.length();int start = -1;int end = -1;int left = 0;int right = 0;int min = Integer.MAX_VALUE;while (left <= right && right < n) {char rightCh = s.charAt(right++);if (map.containsKey(rightCh)) {map.put(rightCh, map.get(rightCh) - 1);}while (allZero(map)) {if (right - left < min) {min = right - left;start = left;end = right;}char leftCh = s.charAt(left++);if (map.containsKey(leftCh)) {map.put(leftCh, map.get(leftCh) + 1);}}}String result = "";if (start != -1) {result = s.substring(start, end);}return result;}public boolean allZero(Map<Character, Integer> map) {for (Map.Entry<Character, Integer> entry : map.entrySet()) {if (entry.getValue() > 0) {return false;}}return true;}
}