🔗 最小覆盖子串

题目来源：76. 最小覆盖子串 – 力扣（LeetCode）

---

📌 题目描述

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

• 覆盖：子串必须包含 t 中的所有字符，包括重复字符。
• 最小窗口：在所有满足条件的子串中，长度最短的那个。
• 若有多个相同长度的最小覆盖子串，返回任意一个即可。

---

✅ 示例解析

示例 1：

• 输入：s = "ADOBECODEBANC", t = "ABC"
• 输出："BANC"
• 解释："BANC" 是唯一包含 'A'、'B'、'C' 的最短子串。

示例 2：

• 输入：s = "a", t = "a"
• 输出："a"
• 解释：s 与 t 相同，直接返回。

示例 3：

• 输入：s = "a", t = "aa"
• 输出：""
• 解释：s 中 'a' 只出现一次，无法覆盖 t 中两个 'a'。

---

⚠️ 提示

• 1 <= s.length, t.length <= 10⁵
• s 和 t 由英文字母组成

---

💡 解法：滑动窗口 + 字符频次统计 —— O(m + n) 时间

class Solution {
    public String minWindow(String s, String t) {
        char[] sarr = s.toCharArray();
        char[] tarr = t.toCharArray();
        int slen = sarr.length, tlen = tarr.length;
        if (slen < tlen) {
            return "";
        }
        int number = 0;
        int[] curr = new int[128];
        for (int i = 0; i < tlen; i++) {
            if (curr[tarr[i]] == 0) {
                number++;
            }
            curr[tarr[i]]++;
        }
        int ansl = -1, ansr = slen - 1, left = 0;
        for (int right = 0; right < slen; right++) {
            curr[sarr[right]]--;
            if (curr[sarr[right]] == 0) {
                number--;
            }
            while (number == 0) {
                if (right - left < ansr - ansl) {
                    ansl = left;
                    ansr = right;
                }
                if (curr[sarr[left]] == 0) {
                    number++;
                }
                curr[sarr[left]]++;
                left++;
            }
        }
        return ansl == -1 ? "" : s.substring(ansl, ansr + 1);
    }
}

---

📊 复杂度分析

• 时间复杂度：O(m + n)
  • m 为 s 的长度，n 为 t 的长度
  • 初始化 t 的字符频次：O(n)
  • 滑动窗口遍历 s：每个字符最多被 right 和 left 各访问一次，O(m)
  • 总体为线性时间。
• 空间复杂度：O(1)
  • 使用固定长度 128 的数组（ASCII 字符集）存储字符频次
  • 空间不随输入规模变化，视为常数空间。

---

🧩 解题思路

1. 滑动窗口框架：
   使用双指针 left 和 right 维护一个窗口 [left, right]，目标是找到能覆盖 t 的最短区间。
2. 频次数组与匹配计数：
   • curr[128]：记录 t 中每个字符的“剩余需求量”。
     • 初始化时，curr[c]++ 表示字符 c 需要被覆盖的次数。
     • 在 s 中每遇到一个 c，curr[c]--，表示需求减少。
   • number：表示当前还有多少种字符的“需求量”尚未满足（即 curr[c] > 0 的种类数）。
     • 当 number == 0 时，说明当前窗口已完全覆盖 t。
3. 窗口扩展（右指针移动）：
   • right 从 0 开始向右移动，将 s[right] 加入窗口。
   • 执行 curr[sarr[right]]--，若减为 0，说明该字符的需求刚好满足，number--。
4. 窗口收缩（左指针移动）：
   • 当 number == 0，说明当前窗口已覆盖 t，尝试收缩 left 以寻找更小的窗口。
   • 在 while (number == 0) 循环中：
     • 比较当前窗口 right - left 是否比已记录的更短，若是则更新 ansl 和 ansr。
     • 将 sarr[left] 移出窗口：
       • 若 curr[sarr[left]] == 0，说明移出后该字符将不再满足需求，number++
       • 执行 curr[sarr[left]]++，恢复其需求量
     • left++，继续收缩。
5. 答案更新：
   • 只有在窗口满足覆盖条件（number == 0）时才更新答案。
   • 使用 ansl == -1 判断是否找到有效解。
6. 边界处理：
   • 若 s.length < t.length，直接返回 ""，不可能覆盖。
   • 初始 ansr = slen - 1，确保第一次更新时能正确比较长度。