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.
1 class Solution { 2 public String minWindow(String s, String t) { 3 4 if(s.length()<t.length()) 5 return ""; 6 Map<Character,Integer> wordDict = constructWordDict(t); 7 8 int slow =0,minLen=Integer.MAX_VALUE,fast=0,matchCount=0,start = 0; 9 for(fast=0;fast<s.length();fast++){ 10 char ch = s.charAt(fast); 11 Integer cnt = wordDict.get(ch); 12 13 //当前字符不在map中,fast++ 14 if(cnt ==null) 15 continue; 16 wordDict.put(ch,cnt-1); 17 18 //当前字符在map中,且 cnt==1,需要这个match, match总数++ 19 if(cnt==1) 20 matchCount++; 21 22 // 如果 match的个数够了,尝试移动slow,使其更短 23 while(matchCount==wordDict.size()){ 24 //更新最短长度 25 if(fast-slow+1<minLen){ 26 minLen = fast-slow+1; 27 start=slow; 28 } 29 //移动slow 30 char left = s.charAt(slow++); 31 Integer leftCnt = wordDict.get(left); 32 //当 slow 对应的字符串不在map中,说明当前字符串不需要match,继续移动 33 if(leftCnt==null) 34 continue; 35 36 //当slow 对应的字符串在map中时,map中的key+1, 37 wordDict.put(left,leftCnt+1); 38 //如果slow对应的元素cnt==0,说明移动过头了,需要重新match slow对应的元素 39 if(leftCnt==0) 40 matchCount --; 41 42 } 43 } 44 return minLen==Integer.MAX_VALUE?"":s.substring(start,start+minLen); 45 } 46 private Map<Character,Integer> constructWordDict(String s){ 47 Map<Character,Integer> map = new HashMap<>(); 48 for(char ch :s.toCharArray()){ 49 Integer cnt = map.get(ch); 50 if(cnt==null) 51 map.put(ch,1); 52 else 53 map.put(ch,cnt+1); 54 } 55 return map; 56 } 57 }
https://www.youtube.com/watch?v=9qFR2WQGqkU