public class Solution {
public String minWindow(String S, String T) {
HashMap<Character,Integer>needToFind=new HashMap<Character,Integer>();
for(char c:T.toCharArray()){
if(needToFind.containsKey(c)){
needToFind.put(c,needToFind.get(c)+1);
}else{
needToFind.put(c,1);
}
}
int found=0;
int min=Integer.MAX_VALUE;
int rstart=0,rend=0;
HashMap<Character,Integer>foundMap=new HashMap<Character,Integer>();
int begin=0;
for(int end=0;end<S.length();end++){
char c=S.charAt(end);
if(!needToFind.containsKey(c))continue;
if(foundMap.containsKey(c)){
foundMap.put(c,foundMap.get(c)+1);
}else{
foundMap.put(c,1);
}
if(foundMap.get(c)<=needToFind.get(c))
found++;
if(found==T.length()){
c=S.charAt(begin);
while(!needToFind.containsKey(c)||
foundMap.get(c)>needToFind.get(c)){
if(needToFind.containsKey(c)){
foundMap.put(c,foundMap.get(c)-1);
}
begin++;
c=S.charAt(begin);
}
if(min>end-begin){
min=end-begin;
rstart=begin;
rend=end;
}
}
}
if(found==T.length())return S.substring(rstart,rend+1);
return "";
}
}