题解 | #最小覆盖子串#

import java.util.*;


public class Solution {
    /**
     * 滑动窗口
     * @param S string字符串 
     * @param T string字符串 
     * @return string字符串
     */
    public String minWindow (String S, String T) {
        // write code here
        int tLen=T.length(),sLen=S.length();
        //T的长度比S大直接返回
        if(tLen>sLen){return "";}
        //tMap记录T中所有字符的数量
        Map<Character,Integer> tMap=new HashMap<>();
        for(int i=0;i<tLen;i++){
            char c=T.charAt(i);
            tMap.put(c,tMap.getOrDefault(c,0)+1);
        }
        //左右指针
        int l=0,r=0,valid=0,size=tMap.size(),tl=0,tr=10001;
        Map<Character,Integer> sMap=new HashMap<>();
        while(r<sLen){
            char c=S.charAt(r);
            if(tMap.containsKey(c)){
                int freq=sMap.getOrDefault(c,0)+1;
                sMap.put(c,freq);
                //如果sMap和tMap的数量一致，说明满足一个字母的数量相等
                if(freq==tMap.get(c)){
                    valid++;
                }
                //如果所有字母数量都相等，移动左指针
                while(l<=r&&valid==size){
                    char cl=S.charAt(l);
                    if(sMap.containsKey(cl)){
                        int cFreq=sMap.get(cl);
                        //左指针移动到tMap和sMap的字母数量一致时，即将不满足题目条件
                        if(cFreq==tMap.get(cl)){
                            //比较临时变量左右距离和现在左右指针的距离
                            if(tr-tl>r-l){
                                tl=l;
                                tr=r+1;
                            }
                            valid--;
                        }
                        sMap.put(cl,cFreq-1);
                    }
                    l++;
                }
            }
            r++;
        }
        return tr-tl==10001?"":S.substring(tl,tr);
    }
}