76. Minimum Window Substring (JAVA)

时间:2024-10-19 13:32:50

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.

重点:

  • 滑动窗口
  • Map的put,get,判断是否存在,遍历
  • String的截取
class Solution {
public String minWindow(String s, String t) {
Map<Character,Integer> target = new HashMap<Character,Integer>();
for(int i = 0; i < t.length(); i++){
if(!target.containsKey(t.charAt(i))) target.put(t.charAt(i),1);
else target.put(t.charAt(i), target.get(t.charAt(i))+1);
} int left = 0;
int right = 0;
int minLength = Integer.MAX_VALUE;
int minLeft = 0;
int minRight = s.length()-1;
Map<Character,Integer> source = new HashMap<Character,Integer>();
source.put(s.charAt(0),1);
while(left<=right){
if(ifContain(source,target)){
if(right-left+1 < minLength){
minLength = right-left+1;
minLeft = left;
minRight = right;
} source.put(s.charAt(left), source.get(s.charAt(left))-1);
left++;
}
else{
right++;
if(right == s.length()) break; if(!source.containsKey(s.charAt(right))) source.put(s.charAt(right),1);
else source.put(s.charAt(right), source.get(s.charAt(right))+1);
}
} if(minLength==Integer.MAX_VALUE) return "";
else return s.substring(minLeft,minRight+1);
} public Boolean ifContain(Map<Character, Integer> source, Map<Character, Integer> target){
for(Character key: target.keySet()){
if(!source.containsKey(key) || source.get(key) < target.get(key)) return false;
}
return true;
}
}