Leetcode 76. 最小覆盖子串

76. 最小覆盖子串 - 力扣（LeetCode）

class Solution {
    /**
    也是滑动窗口，思路简单，但实现起来容易出错。
    一个tmap记录目标串t的各个字符出现的次数；
    一个smap记录原串的某个滑动窗口里字符出现次数。
    两个指针left，right都从0开始，用right遍历原串s，
    如果smap包含了所有tmap的kv，那么肯定就匹配上了，
    这个时候呢，就更新left，进行++操作，每加一次，就看是不是不满足smap包含了所有tmap的kv，
    如果不满足就停止left的++。
     */
    public String minWindow(String s, String t) {
        if(s == null || t==null || s.length()==0 || t.length()==0){
            return "";
        }
        Map<Character,Integer> targetMap=new HashMap<>();
        // 这里其实也可以用charAt
        for(char c:t.toCharArray()){
            targetMap.put(c,targetMap.getOrDefault(c,0)+1);
        }
        int left=0,right=0;
        // t字符串里不同字符的数量
        int tCnt=targetMap.size();

        int sCnt=0;

        //Integer.MAX_VALUE
        int start=0,minLen=1000005;

        Map<Character,Integer> sMap=new HashMap<>();

        while(right<s.length()){
            char c=s.charAt(right);
            sMap.put(c,sMap.getOrDefault(c,0)+1);
            if(targetMap.containsKey(c) && sMap.get(c).intValue()==targetMap.get(c).intValue()){
                sCnt++;
            }

            // right-left-1，因为下标left到right之间字符串的长度范围是right-left+1，减去1等于t.length，这个长度才是真实的临界值
            while(sCnt==tCnt && right-left-1>=t.length()){
                char sc=s.charAt(left);
                if(right-left+1<minLen){
                    start=left;
                    minLen=right-left+1;
                }
                
                sMap.put(sc,sMap.get(sc)-1);
                left++;

                if(targetMap.containsKey(sc) && sMap.get(sc).intValue()<targetMap.get(sc).intValue()){
                // 说明匹配的子串字符种类数不一样了，left就不能再++了
                sCnt--;
                }
            }
            
            right++;
        }

        return minLen==1000005?"":s.substring(start,start+minLen);
    }
}