76. Minimum Window Substring(hard 双指针)

时间:2023-03-08 16:53:08
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.
 class Solution {
public String minWindow(String s, String t) { if(s.length()<t.length())
return "";
Map<Character,Integer> wordDict = constructWordDict(t); int slow =0,minLen=Integer.MAX_VALUE,fast=0,matchCount=0,start = 0;
for(fast=0;fast<s.length();fast++){
char ch = s.charAt(fast);
Integer cnt = wordDict.get(ch); //当前字符不在map中,fast++
if(cnt ==null)
continue;
wordDict.put(ch,cnt-1); //当前字符在map中,且 cnt==1,需要这个match, match总数++
if(cnt==1)
matchCount++; // 如果 match的个数够了,尝试移动slow,使其更短
while(matchCount==wordDict.size()){
//更新最短长度
if(fast-slow+1<minLen){
minLen = fast-slow+1;
start=slow;
}
//移动slow
char left = s.charAt(slow++);
Integer leftCnt = wordDict.get(left);
//当 slow 对应的字符串不在map中,说明当前字符串不需要match,继续移动
if(leftCnt==null)
continue; //当slow 对应的字符串在map中时,map中的key+1,
wordDict.put(left,leftCnt+1);
//如果slow对应的元素cnt==0,说明移动过头了,需要重新match slow对应的元素
if(leftCnt==0)
matchCount --; }
}
return minLen==Integer.MAX_VALUE?"":s.substring(start,start+minLen);
}
private Map<Character,Integer> constructWordDict(String s){
Map<Character,Integer> map = new HashMap<>();
for(char ch :s.toCharArray()){
Integer cnt = map.get(ch);
if(cnt==null)
map.put(ch,1);
else
map.put(ch,cnt+1);
}
return map;
}
}

https://www.youtube.com/watch?v=9qFR2WQGqkU