力扣经典150题第三十三题：最小覆盖子串

解题思路与实现 - 最小覆盖子串

问题描述

给定一个字符串 s 和一个字符串 t，返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 ""。

示例

1. 输入：s = “ADOBECODEBANC”, t = “ABC”
   输出：“BANC”
   解释：最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、‘B’ 和 ‘C’。

2. 输入：s = “a”, t = “a”
   输出：“a”
   解释：整个字符串 s 是最小覆盖子串。

3. 输入：s = “a”, t = “aa”
   输出：“”
   解释：t 中两个字符 ‘a’ 均应包含在 s 的子串中，因此没有符合条件的子字符串，返回空字符串。

解题思路

使用滑动窗口（双指针）和哈希表的方法解决该问题：

1. 使用哈希表 targetCount 记录字符串 t 中每个字符的出现次数。
2. 使用两个指针 left 和 right 维护滑动窗口，初始时两者都指向字符串开头。
3. 遍历字符串 s，右指针 right 向右移动，将字符加入窗口，并更新窗口内字符的计数。
4. 当窗口包含了 t 中所有字符且满足条件时，移动左指针 left 缩小窗口，尝试找到最小的覆盖子串。
5. 更新最小覆盖子串的起始位置和长度。

算法实现

public String minWindow(String s, String t) {
    if (s == null || s.isEmpty() || t == null || t.isEmpty() || s.length() < t.length()) {
        return "";
    }
    
    // 统计 t 中每个字符的出现次数
    Map<Character, Integer> targetCount = new HashMap<>();
    for (char c : t.toCharArray()) {
        targetCount.put(c, targetCount.getOrDefault(c, 0) + 1);
    }
    
    int left = 0, right = 0;
    int minLen = Integer.MAX_VALUE;
    int start = 0;
    int requiredChars = targetCount.size(); // 需要覆盖的字符种类数
    int formed = 0; // 已经覆盖的字符种类数
    
    Map<Character, Integer> windowCount = new HashMap<>();
    
    while (right < s.length()) {
        char currentChar = s.charAt(right);
        windowCount.put(currentChar, windowCount.getOrDefault(currentChar, 0) + 1);
        
        if (targetCount.containsKey(currentChar) && windowCount.get(currentChar).intValue() == targetCount.get(currentChar).intValue()) {
            formed++;
        }
        
        // 尝试缩小窗口
        while (left <= right && formed == requiredChars) {
            int currentLen = right - left + 1;
            if (currentLen < minLen) {
                minLen = currentLen;
                start = left;
            }
            
            char leftChar = s.charAt(left);
            windowCount.put(leftChar, windowCount.get(leftChar) - 1);
            if (targetCount.containsKey(leftChar) && windowCount.get(leftChar).intValue() < targetCount.get(leftChar).intValue()) {
                formed--;
            }
            
            left++;
        }
        
        right++;
    }
    
    return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}

复杂度分析

• 时间复杂度：O(m + n)，其中 m 是字符串 s 的长度，n 是字符串 t 的长度。
• 空间复杂度：O(m + n)，使用了两个哈希表来存储字符出现次数。

测试与验证

设计不同测试用例，包括空字符串、单个字符、多个字符等情况，验证算法的正确性和效率。

总结

通过本文的详细解题思路和算法实现，可以有效地解决给定字符串中涵盖指定字符集合的最小子串问题。利用滑动窗口和哈希表的方法，可以高效地实现该算法。

感谢阅读！