解题思路与实现 - 最小覆盖子串
问题描述
给定一个字符串 s 和一个字符串 t，返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 ""。
示例
- 输入：s = “ADOBECODEBANC”, t = “ABC”
输出：“BANC”
解释：最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、‘B’ 和 ‘C’。 - 输入：s = “a”, t = “a”
输出：“a”
解释：整个字符串 s 是最小覆盖子串。 - 输入：s = “a”, t = “aa”
输出：“”
解释：t 中两个字符 ‘a’ 均应包含在 s 的子串中，因此没有符合条件的子字符串，返回空字符串。
解题思路
使用滑动窗口（双指针）和哈希表的方法解决该问题：
- 使用哈希表 targetCount 记录字符串 t 中每个字符的出现次数。
- 使用两个指针 left 和 right 维护滑动窗口，初始时两者都指向字符串开头。
- 遍历字符串 s，右指针 right 向右移动，将字符加入窗口，并更新窗口内字符的计数。
- 当窗口包含了 t 中所有字符且满足条件时，移动左指针 left 缩小窗口，尝试找到最小的覆盖子串。
- 更新最小覆盖子串的起始位置和长度。
算法实现
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)，使用了两个哈希表来存储字符出现次数。
测试与验证
设计不同测试用例，包括空字符串、单个字符、多个字符等情况，验证算法的正确性和效率。
总结
通过本文的详细解题思路和算法实现，可以有效地解决给定字符串中涵盖指定字符集合的最小子串问题。利用滑动窗口和哈希表的方法，可以高效地实现该算法。
