Java 滑动窗口进阶：带条件判断的「最小覆盖子串」解题全流程

问题定义与难点解析

在字符串处理中，最小覆盖子串问题要求找出字符串$s$中包含字符串$t$所有字符的最短连续子串。进阶版本需满足三个核心条件：

1. 子串必须包含$t$中所有字符（包括重复字符）
2. 时间复杂度必须控制在$O(n)$级别
3. 需动态处理字符频次匹配条件

示例说明

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

难点在于当$t$包含重复字符时（如$t="AABC"$），需确保子串中字符频次精确匹配。

算法核心思想

采用双指针滑动窗口框架，加入条件计数器机制：

$$\text{窗口状态} = \begin{cases} \text{扩展右边界} & \text{当 } \text{条件不满足} \ \text{收缩左边界} & \text{当 } \text{条件满足} \end{cases}$$

定义关键变量：

• $need$：哈希表存储$t$中字符频次需求
• $window$：哈希表记录当前窗口字符统计
• $valid$：计数器跟踪满足条件的字符数

当$valid = need.size()$时，窗口满足覆盖条件。

Java实现详解

import java.util.HashMap;

class Solution {
    public String minWindow(String s, String t) {
        // 初始化需求映射
        HashMap<Character, Integer> need = new HashMap<>();
        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        
        // 滑动窗口状态变量
        HashMap<Character, Integer> window = new HashMap<>();
        int left = 0, right = 0;
        int valid = 0; // 满足条件的字符计数
        int start = 0, minLen = 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))) {
                    valid++;
                }
            }
            
            // 条件满足时收缩左边界
            while (valid == need.size()) {
                // 更新最小覆盖子串
                if (right - left < minLen) {
                    start = left;
                    minLen = right - left;
                }
                
                // 移出左边界字符
                char d = s.charAt(left++);
                if (need.containsKey(d)) {
                    // 关键条件判断：移出后是否破坏满足条件状态
                    if (window.get(d).equals(need.get(d))) {
                        valid--;
                    }
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }
}

关键条件判断解析

1. 频次精确匹配

if (window.get(c).equals(need.get(c))) 

确保字符$c$在窗口中出现次数恰好等于需求次数，而非简单存在

1. 条件破坏检测

if (window.get(d).equals(need.get(d))) 

当移出字符$d$导致其窗口频次从满足变为不满足时，更新$valid$计数器

1. 动态边界调整

• 右指针$right$单向前移保证$O(n)$复杂度
• 左指针$left$仅在条件满足时移动

复杂度分析

• 时间复杂度：$O(|s| + |t|)$
  每个字符最多被左右指针各访问一次
• 空间复杂度：$O(|C|)$
  $C$为字符集大小，哈希表存储开销

边界处理技巧

1. 空输入处理

if (s == null || t == null || s.length() == 0 || t.length() == 0) 
return "";

1. 无效解检测

return minLen == Integer.MAX_VALUE ? "" : ... 

1. 整型比较陷阱
   使用.equals()而非==比较Integer对象

算法优化方向

1. 数组替代哈希表
   当字符集为ASCII时，可用int[128]提升性能
2. 需求预检查
   提前判断$|s| < |t|$直接返回空串
3. 无效字符跳过
   预处理$s$剔除$t$中不存在的字符

应用场景扩展

该算法框架可扩展至：

1. 包含所有字符的最短子数组
2. 最多包含K个不同字符的子串
3. 变位词（Anagram）检测

掌握带条件判断的滑动窗口实现，能解决80%以上的字符串子串匹配问题。核心在于精确控制窗口状态转换条件，并设计高效的状态更新机制。