题解 | #最小覆盖子串#

import java.util.*;


public class Solution {
    /**
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return string字符串
     */
    public String minWindow (String S, String T) {
        int [] hash = new int[128];
        for(int i = 0;i <T.length();i ++){
            hash[T.charAt(i)]++;
        }
        //记录滑动窗口
        int fast = 0;
        int slow = 0; 
        //记录结果
        int res = Integer.MAX_VALUE;
        String reStr = "";
        if(S.length() < T.length()) return reStr;
        while(fast < S.length()){
            //fast向右扩展直到有匹配的字符串
            fast++;
            //利用T字符串和slow，fast之间的字符串进行验证，每次验证成功之后比对res是否比较小，然后slow++,窗口移动
            while(check(hash,S.substring(slow,fast))){
                if(fast-slow <= res){
                    res = fast-slow;
                    reStr = S.substring(slow,fast);
                }
                //移动到不匹配开始移动右指针
                slow++;
            }
        }
        return reStr;
    
    }

    /**
     *  检查字符串中是否符合匹配
     */
    public boolean check(int [] cnt,String S){
        int [] tmp = new int[128];
        for(int i = 0;i < S.length();i ++){
            if(cnt[S.charAt(i)] > 0){
                //当字符串S中已经包含某个字符，则不需要再累加，因为最后判断是否match是通过数组的相等
                if(tmp[S.charAt(i)] == cnt[S.charAt(i)]) continue;
                tmp[S.charAt(i)]++;
            }
        }
        if(Arrays.equals(tmp,cnt)) return true;
        return false;
    }
}