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;

     }

 }