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;
}
}