【leetcode每日刷题】【hard】76. Minimum Window Substring

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:

Input: S = "ADOBECODEBANC", T = "ABC" Output: "BANC"

Note:

If there is no such window in S that covers all characters in T, return the empty string "".If there is such window, you are guaranteed that there will always be only one unique minimum window in S. import java.util.HashMap; import java.util.Map; class num76{ public String minWindow(String s, String t) { if(s.length()==0 || t.length()==0) return ""; Map<Character, Integer> dict = new HashMap<Character,Integer>(); for(int i=0; i<t.length(); i++){ int count = dict.getOrDefault(t.charAt(i), 0); dict.put(t.charAt(i), count+1); } int required = dict.size(); int formed = 0; int l=0, r =0; Map<Character, Integer> windowCount = new HashMap<Character, Integer>(); int[] ans={-1, 0, 0}; while(r<s.length()){ char c = s.charAt(r); int count = windowCount.getOrDefault(c, 0); windowCount.put(c, count+1); if(dict.containsKey(c) && dict.get(c).intValue() == windowCount.get(c).intValue()) formed ++; while(l<=r && formed==required){ c = s.charAt(l); if(ans[0]==-1||r-l+1<ans[0]){ ans[0] = r-l+1; ans[1] = l; ans[2] = r; } windowCount.put(c,windowCount.get(c)-1); if(dict.containsKey(c) && windowCount.get(c).intValue() < dict.get(c).intValue()) formed--; l++; } r++; } return ans[0] == -1? "" : s.substring(ans[1], ans[2]+1); } }

最后的一个超级长的case没有过, 是因为哈希表中dict.get(c)的时候获得的是Integer对象，而不是int类型的数据，所以需要使用dict.get(c).intValue()转换一下。

jjie'ti

 使用字典dict维护字符串T中的字符和字符的个数，使用空间大小为3的ans数组维护最短的长度以及字符串S的左边界和右边界。使用windowCount维护字符串S的l到r边界中间的字符以及个数，使用formed维护S子字符串中和T中字符个数已经相等的个数。

算法的步骤为：右边界 r 一直向右移动直到S子字符串中包含字典中的所有字符和个数。当子字符串中已经包括所有字典中的字符和个数后，开始移动左指针去除可能多余的字符，得出最小的子串长度。此时再移动右边界，一直这样循环。