76. 最小覆盖字串

class Solution {
    public String minWindow(String s, String t) {
        int sLength = s.length();
        int tLength = t.length();
        int leftIndex = 0;
        int rightIndex = 0;
        // 滑动窗口的开始位置
        int start = 0; 

        // 统计t中出现的字符及其个数
        HashMap<Character, Integer> windowMap = new HashMap<>();
        HashMap<Character, Integer> tMap = new HashMap<>();
        for(char c:t.toCharArray()) {
            tMap.put(c, tMap.getOrDefault(c, 0) + 1);
        }
        // 最终滑动窗口的长度
        int resultLength = Integer.MAX_VALUE;
        // s覆盖t的长度
        int validLength = 0;

        // 先扩大右边界，用窗口覆盖t,s的字串不需要连续
        // 覆盖的意思是窗口中各个字符的数量等于t中各个字符的数量
        // 收缩左边界，找到最小值
        while(rightIndex < sLength) {
            char c = s.charAt(rightIndex);
            rightIndex++;
            if(tMap.containsKey(c)) {
                windowMap.put(c, windowMap.getOrDefault(c, 0) + 1);
                // 某个字符的数量对上了。
                if(windowMap.get(c).equals(tMap.get(c))) {
                    validLength++;
                }
            }
            // s已经覆盖t，然后进行收缩
            while (validLength == tMap.size()) {
                if (rightIndex - leftIndex < resultLength) {
                    resultLength = rightIndex - leftIndex;
                    start = leftIndex; 
                }
                char cS = s.charAt(leftIndex);
                leftIndex++;
                if (tMap.containsKey(cS)) {
                    if (windowMap.get(cS).equals(tMap.get(cS))) {
                        validLength--;
                    }
                    windowMap.put(cS, windowMap.getOrDefault(cS, 0) - 1);
                }
            }
        }
        if (resultLength == Integer.MAX_VALUE) {
            return "";
        } else {
            return s.substring(start, start + resultLength);
        }
    }
}