🌕 🌗 76. 最小覆盖子串

难度: 🌕 🌗

• 问题描述
• 解法
• 输出

问题描述

---

解法

class Solution {
    public String minWindow(String s, String t) {
        // 思路:
        // 滑动窗口
        // HashMap 记录 t 所需各个字符的数量
        // 增大右窗口找到满足条件的右边界
        // 尝试能否缩小左边界
        int len = s.length();
        int amount = t.length();
        // 特殊情况特判
        if(len < amount) {
            return "";
        }
        int res = len + 1;
        int[] dp = new int[2];
        int left = 0;
        int right = 0;
        // 遍历 t 填充 map
        HashMap<Character, Integer> map = new HashMap<>();
        for(char c : t.toCharArray()) {
            if(!map.containsKey(c)) {
                map.put(c, 1);
            } else {
                int count = map.get(c);
                count ++;
                map.put(c, count);
            }
        }
        // 滑动窗口遍历 s
        while(left < len) {
            // 找右边界
            while(right < len && amount > 0) {
                char cur = s.charAt(right);
                // 判断当前是否缺少 cur 这个字符
                if(map.containsKey(cur)) {
                    int count = map.get(cur);
                    if(count > 0) {
                        // 表示还需要 count 个该字符
                        count --;
                        map.put(cur, count);
                        amount --;
                    } else {
                        // 需要该字符，但目前该字符数已经足够
                        count --;
                        map.put(cur, count);
                    }
                }
                if(amount == 0) {
                    break;
                }
                right ++;
            }
            // System.out.println("left : " + left + " right : " + right);
            if(right == len) {
                break;
            }
            // 看能否缩进左边界
            while(left < right) {
                char cur = s.charAt(left);
                if(!map.containsKey(cur)) {
                    left ++;
                } else {
                    // 需要该字符
                    // 判断该字符是否多余
                    int count = map.get(cur);
                    // System.out.println("缩进左边界  - cur: " + cur + " count: " + count);
                    if(count < 0) {
                        // 多出来了 count 张无用字符
                        count ++;
                        map.put(cur, count);
                        left ++;
                    } else {
                        // 该字符不能去掉
                        break;
                    }
                }
            }
            // System.out.println("  ----------  left : " + left + " right : " + right);
            res = Math.min(res, right - left + 1);
            if(res == right - left + 1) {
                dp[0] = left;
                dp[1] = right;
            }
            // 左边界往前推进一个当前所需字符
            right ++; // right 之前计算时为右闭区间，为防止重复计算，需要 ++
            char rv = s.charAt(left);
            amount ++;
            map.put(rv, 1);
            left ++;
            while(left < right) {
                char cur = s.charAt(left);
                if(!map.containsKey(cur)) {
                    left ++;
                } else {
                    // 需要该字符
                    int count = map.get(cur);
                    if(count < 0) {
                        count ++;
                        map.put(cur, count);
                        left ++;
                    } else {
                        break;
                    }
                }
            }
        }
        if(res == len + 1) {
            return "";
        }
        return s.substring(dp[0], dp[1] + 1);
    }
}

---

输出