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