76. 最小覆盖子串

题目：最小覆盖子串

描述：

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

---

示例：

示例 1:

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

示例 2:

输入: s = "ADOBECODEBANC", t = "AB"
输出: "AB"

示例 3:

输入: s = "a", t = "aa"
输出: ""

---

解题思路

问题分析

我们需要找到 s 中的最短子串，使其包含 t 中的所有字符，且每个字符的数量也符合 t 中的要求。

• 包含所有字符的含义：
  • 子串中必须包含 t 中的每个字符，且数量不能少于 t 中对应的数量。例如：
    • 对于 t = "ABC"，子串中必须有 A、B 和 C，每个字符至少出现一次。

为什么选择滑动窗口？

滑动窗口非常适合解决子串相关的问题，因为它可以动态地调整范围并维护需要的条件：

• 滑动窗口通过双指针（left 和 right）维护一个子串的范围 [left, right)。
• 在滑动过程中，动态记录窗口中的字符频率，判断窗口是否满足 t 的需求。

---

实现步骤

核心操作：

1. 哈希表维护需求：

   • 用一个 need 哈希表存储 t 中每个字符的需求数量。
   • 用另一个 window 哈希表存储当前窗口中字符的数量。

2. 移动右指针扩展窗口：

   • 右指针每次移动一格，将字符加入 window，并更新其频率。
   • 如果窗口中某个字符的数量满足了 need 中的需求，则增加 valid 计数。

3. 移动左指针收缩窗口：

   • 当窗口满足 t 中所有字符的需求时，尝试通过移动左指针缩小窗口，找到更小的满足条件的子串。
   • 如果某个字符从窗口中移除后导致不再满足需求，减少 valid 计数。

4. 更新最小子串：

   • 每次窗口满足需求时，更新最小子串的起始位置和长度。

5. 边界处理：

   • 如果整个字符串 s 遍历完，未找到满足条件的子串，则返回空字符串。

---

代码实现

import java.util.HashMap;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        String s = scanner.next();
        String t = scanner.next();

        Solution solution = new Solution();
        String result = solution.minWindow(s, t);
        System.out.println(result);

        scanner.close();
    }
}

class Solution {
    public String minWindow(String s, String t) {
        if (s == null || t == null || s.length() < t.length()) {
            return "";
        }

        // 哈希表记录 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);
            right++; // 移动右指针
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c).intValue() == need.get(c).intValue()) {
                    valid++;
                }
            }

            // 收缩窗口
            while (valid == need.size()) {
                // 更新最小子串
                if (right - left < minLen) {
                    minLen = right - left;
                    start = left;
                }

                // 移除窗口左边的字符
                char d = s.charAt(left);
                left++; // 移动左指针
                if (need.containsKey(d)) {
                    if (window.get(d).intValue() == need.get(d).intValue()) {
                        valid--;
                    }
                    window.put(d, window.get(d) - 1);
                }
            }
        }

        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }
}

---

代码逻辑解析

示例：s = "ADOBECODEBANC", t = "ABC"

1. 初始化：

   • need = {A:1, B:1, C:1}
   • window = {}，valid = 0
   • left = 0, right = 0

2. 扩展窗口：

   • 当右指针移动时，将字符 s[right] 加入 window，更新窗口内字符的频率。
   • 如果窗口内的某字符数量满足 need 中对应的需求，则增加 valid 计数。

3. 收缩窗口：

   • 当 valid == need.size() 时，说明当前窗口已经包含了 t 中所有字符。
   • 移动左指针 left，尝试缩小窗口，找出更短的符合条件的子串。

4. 更新结果：

   • 每次窗口满足条件时，检查当前窗口长度是否为最小，更新最小子串的起始位置和长度。

---

时间复杂度

1. 遍历字符串：双指针遍历字符串 s，时间复杂度为 O(n)。
2. 更新哈希表：每次对 need 和 window 的操作都是常数时间 O(1)。

总时间复杂度：O(n)。

---

空间复杂度

1. 哈希表存储：need 和 window 哈希表的大小最多为字符集的大小（假设是英文字母，则为常数 O(26)）。

总空间复杂度：O(m)，其中 m 是字符集大小。

---

总结

• 为什么选择滑动窗口？
  • 滑动窗口是解决字符串子串问题的高效方法，可以动态维护一个范围并高效判断条件是否满足。
• 优化点：
  • 通过双哈希表和有效字符计数器 valid，可以在 O(n) 时间内判断窗口是否满足条件。