题解 | #最小覆盖子串#

思路:滑动窗口

• 核心：什么条件下，才更新窗口中的数据。
• 思考1：当移动右指针right扩大窗口时，到达当前字符，需要做什么事，更新哪些数据，求可行解？
• 思考2：什么条件下，窗口应该暂停扩大，开始移动left来缩小窗口,求最优解？
• 思考3：当移动左指针left缩小窗口时，到达当前字符，需要做什么事，更新哪些数据，求最优解？
• 思考4：需要的最优解应该在扩大窗口时更新，还是在缩小窗口时更新?
• 如果一个字符进入窗口，应该增加 window 计数器；如果一个字符将移出窗口的时候，应该减少 window 计数器；当 valid 满足 need 时应该收缩窗口；应该在收缩窗口的时候更新最终结果。

import java.util.*;


public class Solution {
    /**
     *
     * @param S string字符串
     * @param T string字符串
     * @return string字符串
     */
    public String minWindow (String S, String T) {
        // write code here
        HashMap<Character, Integer> need = new HashMap<>();
        HashMap<Character, Integer> window = new HashMap<>();
        for (int i = 0; i < T.length(); ++i) {
            char ch = T.charAt(i);
            need.put(ch, need.getOrDefault(ch, 0) + 1);
        }
        int left = 0, right = 0; // 左闭右开的窗口
        int valid = 0;
        // 记录最小覆盖子串的开始索引和长度
        int start = 0, len = Integer.MAX_VALUE;
        while (right < S.length()) {
            char c = S.charAt(right);
            // 当右指针到达某个字符时要做的事
            if (need.containsKey(c)) { // 目标字符串包含该字符串时，才更新窗口
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c).equals(need.get(c))) { // 窗口中的当前字符c已经满足需求
                    valid++;
                }
            }
            ++right; // 扩大窗口

            while (valid == need.size()) { // 找到第一个满足need的位置，窗口停止扩大
                // 计算窗口起点和长度
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }
                // 左指针到达某个字符时需要做的事
                char d = S.charAt(left);
                if (window.containsKey(
                            d)) { // 窗口中包含当前字符d，需要更新窗口
                    if (window.get(d).equals(need.get(d))) { // 数目匹配
                        valid--;
                    }
                    window.put(d, window.get(d) - 1);
                }
                ++left;  // 缩小窗口
            }
        }

        //System.out.println("left: " + left + ", right: " + right);
        StringBuilder res = new StringBuilder();
        if (len != Integer.MAX_VALUE) {
            for (int i = start; i < start + len; i++) {
                res.append(S.charAt(i));
            }
        }
        return new String(res);
        // return len == Integer.MAX_VALUE ? "" : S.substring(start, start + len);
    }
}