题解 | #最小覆盖子串#

import java.util.*;


public class Solution {
    /**
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return string字符串
     */
     /**
        思路：使用双指针 left 和 right 
        使用两个map 分别表示当前窗口中的字符统计window 和 需要的字符统计need
        然后 right 一直右移 直到当前window中包含我们所需要的need
        即window中的字符统计 和 need中的字符统计相等为止
        此时左移 选出尽可能短的符合要求的window  然后记录下来 直至不符合要求为止
        然后再次右移   直到当前window中包含我们所需要的need
        此时再次左移 选出尽可能短的符合要求的window  然后记录下来 直至不符合要求为止
        。。。。
        重复上面操作直至 right 超出范围
      */
    public String minWindow (String S, String T) {
        // write code here
        String res = S;
        boolean flag = false;

        int n = S.length() - T.length();
        //如果S的长度小与T 那么S一定不包含T
        if(n < 0 ) return "";

        //记录当前 窗口中的每个字符的个数
        HashMap<Character,Integer> window = new HashMap<>();
        //记录T中我们所需要的每个字符的个数
        HashMap<Character,Integer> need = new HashMap<>();

        //初始化window中每个字符为0
        for(int i = 0 ; i < S.length() ; i++){
            char c = S.charAt(i);
            if(!window.containsKey(c)){
                window.put(c,0);
            }
        }

        //根据T初始化need中所需要的每个字符的统计
        for(int i = 0 ; i < T.length() ; i++){
            char c = T.charAt(i);
            if(!need.containsKey(c)){
                need.put(c,1);
            }else{
                need.put(c,need.get(c)+1);
            }
        }

        //定义双指针
        int left = 0;
        int right = 0;
        //定义 一个start 和一个 len 来唯一确定一个字符串
        int start = 0;
        int len = Integer.MAX_VALUE;
        // 表示当前子串s 和 目标串T的匹配程度  （错误）当match == T.length 时匹配
        //                                   （正确）当match == need.size()
        int match = 0;

        while(right < S.length()){
            while(match != need.size() && right < S.length()){
                char c = S.charAt(right);
                //如果整个字符是属于T中的
                if(need.containsKey(c)){
                    window.put(c,window.get(c)+1);
                    //如果当前need中的c的个数刚好符合要求 
                    //这里 如果window中的c多了 也不会增加match 
                    if(window.get(c) == need.get(c)){
                        match ++;
                    }
                }
                right++;            
            }

            //此时window中已经包含T


            while(match == need.size()){  //只要window中的字符串包含S
                //这里记录 当前最短合规字符串window

                if(right - left < len){
                    len = right - left;
                    start = left;
                }
    
                char c = S.charAt(left);
                //如果left这个字符是当前所被需要的
                if(need.containsKey(c)){
                    window.put(c,window.get(c) -1);
                    //去除window中的字符影响到了window包含T
                    if(window.get(c) < need.get(c)){
                            match--;
                    }
                }
                left++;
            }

        }   
      
        return len == Integer.MAX_VALUE?"":S.substring(start,start+len);
        
    }
}