76.最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 “” 。
注意:
对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串,我们保证它是唯一的答案。
class Solution {public String minWindow(String s, String t) {String minstr = "";Map<Character,Integer> need = new HashMap<>();Map<Character,Integer> win = new HashMap<>();for(char c : t.toCharArray()){need.put(c,need.getOrDefault(c,0)+1);}int left = 0, right = 0, tagl = 0;int size = 0, minLen = Integer.MAX_VALUE;while(right < s.length()){char cr = s.charAt(right);right++;if(need.containsKey(cr)){win.put(cr,win.getOrDefault(cr,0)+1);//这里使用==就会有bugif(win.get(cr).equals(need.get(cr))){size++;}}while(size == need.size()){//因为right已经+1了if(right - left < minLen){minLen = right - left;tagl = left;}char cl = s.charAt(left);left++;if(need.containsKey(cl)){//这里使用==就会有bugif(win.get(cl).equals(need.get(cl)))size--;win.put(cl,win.get(cl)-1);}}}return minLen == Integer.MAX_VALUE ? "":s.substring(tagl,tagl+minLen);}
}