76. 最小覆盖子串#

// 通用的滑动窗口模板
public String slidingWindowTemplate(String s, String t) {
    // 1) window：记录“当前窗口”中每个字符出现次数
    Map<Character, Integer> window = new HashMap<>();
    // 2) need：记录“目标字符串 t”中每个字符需要出现的次数
    Map<Character, Integer> need = new HashMap<>();

    // 3) 先遍历 t，把每个目标字符及其需求次数填入 need
    for (char c : t.toCharArray()) {
        need.put(c, need.getOrDefault(c, 0) + 1); // 若字符首次出现则从 0 开始累加
    }

    // 4) left/right 分别是窗口左右边界（左闭右开区间 [left, right)）
    int left = 0, right = 0;
    // 5) valid 表示“已经满足 need 要求的字符种类数”
    int valid = 0;

    // 6) 外层循环：不断右移 right 扩大窗口
    while (right < s.length()) {
        char c = s.charAt(right); // 读取将进入窗口的字符
        right++;  // 右边界右移一格，表示把 c 纳入窗口

        // 7) 根据题目要求，更新 window/valid 等窗口状态
        ...

        // 8) 当窗口满足条件或超出限制时，进入内层循环收缩左边界
        while (window needs shrink) {
            char d = s.charAt(left); // 读取将移出窗口的字符
            left++;  // 左边界右移一格，表示把 d 移出窗口

            // 9) 根据题目要求，回滚/更新 window/valid 等状态
            ...
        }
    }
    return 最终结果; // 返回题目需要的输出（最值、计数、下标或子串）
}

public String minWindow(String s, String t) {
    Map<Character, Integer> need = new HashMap<>(); // 记录 t 中每个字符“需要”的次数
    for (char c : t.toCharArray()) {
        need.put(c, need.getOrDefault(c, 0) + 1); // 构建需求表：字符 -> 需求频次
    }

    Map<Character, Integer> window = new HashMap<>(); // 记录当前滑动窗口中字符出现次数

    int left = 0, right = 0;  // 左右指针，窗口区间为 [left, right)
    int valid = 0;    // 已满足“所需次数”的字符种类数（不是字符总个数）

    int start = 0, minLen = Integer.MAX_VALUE; // 记录最短合法窗口的起点和长度

    while (right < s.length()) {
        char c = s.charAt(right); // 取出将要进入窗口的字符
        right++; // 右边界右移，窗口扩大

        // 只有当 c 是目标字符时，才需要更新窗口计数
        if (need.containsKey(c)) {
            window.put(c, window.getOrDefault(c, 0) + 1); // 更新窗口中 c 的出现次数
            // 当某字符在窗口中的次数“刚好达到”需求次数时，满足种类数 +1
            if (window.get(c).equals(need.get(c))) {
                valid++;
            }
        }

        // 当 valid == need.size() 时，说明当前窗口已覆盖 t 的所有字符需求
        while (valid == need.size()) {
            // 先尝试用当前合法窗口更新答案（目标是最短）
            if (right - left < minLen) {
                start = left; // 记录更优答案的起点
                minLen = right - left; // 记录更优答案的长度
            }

            char d = s.charAt(left); // 取出将要移出窗口的字符
            left++; // 左边界右移，窗口收缩

            // 若 d 是目标字符，需要同步维护 window 和 valid
            if (need.containsKey(d)) {
                // 如果移除前 d 的数量正好满足需求，移除后将不再满足，valid 要减 1
                if (window.get(d).equals(need.get(d))) {
                    valid--;
                }
                window.put(d, window.get(d) - 1); // 再将 d 的窗口计数减 1
            }
        }
    }

    return minLen == Integer.MAX_VALUE ? ""  // 若从未找到合法窗口，返回空字符串
           : s.substring(start, start + minLen); // 否则按记录的起点和长度截取最小覆盖子串
}

S = "ADOBEC"
T = "ABC"

1. 初始状态：
need = {A:1, B:1, C:1}
window = {}
valid = 0

2. 遇到'A'：
window = {A:1}
valid = 1  // A达到要求

3. 遇到'D'：
不是需要的字符，跳过

4. 遇到'O'：
不是需要的字符，跳过

5. 遇到'B'：
window = {A:1, B:1}
valid = 2  // B达到要求

6. 遇到'E'：
不是需要的字符，跳过

7. 遇到'C'：
window = {A:1, B:1, C:1}
valid = 3  // 所有字符都达到要求了

8. 开始收缩窗口...