题解 | #最小覆盖子串#

import java.util.*;


public class Solution {
    /**
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return string字符串
     */
    public String minWindow (String S, String T) {
        // write code here
        Map<Character,Integer> s_map = new HashMap<>();
        Map<Character,Integer> t_map = new HashMap<>();
        //T中的数据存入t_map
        for(int i = 0;i<T.length();i++){
            t_map.put(T.charAt(i), t_map.containsKey(T.charAt(i)) ? t_map.get(T.charAt(i))+1 : 1 );
        }
        int left = 0;
        int right = 0;
        int result_length = Integer.MAX_VALUE;
        String ans = "";
       while(right < S.length()){
           s_map.put(S.charAt(right), s_map.containsKey(S.charAt(right)) ? s_map.get(S.charAt(right)) +1 : 1 );
           while(isCover(s_map,t_map)){
               if(result_length > right - left +1){
                   result_length = right - left +1;
                   ans = S.substring(left,right+1);
               }
                s_map.put(S.charAt(left), s_map.get(S.charAt(left)) - 1 );
                if(s_map.get(S.charAt(left)) == 0){
                    s_map.remove(S.charAt(left));
                }
                left++;
           }
           right++;
       }
        return ans;
    }

    public boolean isCover(Map<Character,Integer> s_map,Map<Character,Integer> t_map){
        for(Character key : t_map.keySet()){
            if(!s_map.containsKey(key)){
                return false;
            }else if(s_map.get(key) < t_map.get(key)){
                return false;
            }
            
        }
        return true;
    }
}