76.最小覆盖子串

class Solution {
    //建立两个hashMap，ori用于存储目标字符串t中每个字符的出现次数
    //cnt用于存储当前窗口中每个字符的出现次数
    Map<Character,Integer> ori = new HashMap<Character,Integer>();
    Map<Character,Integer> cnt = new HashMap<Character,Integer>();

    public String minWindow(String s, String t) {
        int tlen = t.length();

        //遍历目标字符串t,将每个字符及其出现次数存入ori中
        for(int i = 0; i<tlen ; i++){
            char c = t.charAt(i);
            ori.put(c,ori.getOrDefault(c,0)+1);
        }

        int l =0,r = -1; // l窗口左边界，r窗口有边界
        //ansL和ansR用于存储最小覆盖子串的起始位置和结束位置
        int len = Integer.MAX_VALUE,ansL = -1,ansR = -1;
        //s串长度
        int slen = s.length();
        //符合要求的字符数
        int vaild = 0;
        //开始遍历
        while(r < slen){
            ++r;
            //遍历原字符串s,右指针r向右移动，若r未越界且当前字符存在于ori中，则将其添加至cnt中并增加其出现次数
            if(r < slen && ori.containsKey(s.charAt(r))){
                //存放窗口内不同目标字符的数量
                cnt.put(s.charAt(r),cnt.getOrDefault(s.charAt(r),0) + 1);
                //如果对应字符的数量相等了，符合要求的字符数+1
                if(cnt.get(s.charAt(r)).equals(ori.get(s.charAt(r)))) vaild++;
            }

            //判定是否合法
            while(ori.size() == vaild && l<=r){
                //比较窗口大小，如果你后面符合的窗口都比现在大，就没必要更新了，继续缩短窗口
                if(r - l + 1 < len){
                    len = r - l + 1;   //更新为窗口大小
                    ansL = l;  //符合的左边边界下标就是窗口的左边界
                    ansR  = l + len; //符合的右边边界下标
                }

                //若左指针指向的字符存在于ori中，则在cnt中减少其出现次数(因为现在开始向右移动窗口的左边界)
                //如果是普通字符就只是简单的移动指针就可以了，如果是目标字符，就要减少窗口这个字符的数量
                if(ori.containsKey(s.charAt(l))){
                    //如果当前数量和需要的数量是一样的，现在减掉了1，就已经不符合了
                    if(ori.get(s.charAt(l)).equals(cnt.get(s.charAt(l)))) vaild--;
                    cnt.put(s.charAt(l),cnt.getOrDefault(s.charAt(l),0) - 1);
                }
                ///窗口左边界向右移动，缩小窗口
                ++l;
            }
        }
        //返回最小覆盖子串，若ansL为-1,则说明不存在，返回空串，否则，返回s中从ansL到ansR的子串
        return ansL == -1 ? "" : s.substring(ansL, ansR);
    }
}