76 最小覆盖子串

一、题目

给定两个字符串 s 和 t，长度分别是 m 和 n，返回 s 中的 最短窗口 子串，使得该子串包含 t 中的每一个字符（包括重复字符）。如果没有这样的子串，返回空字符串 ""。

测试用例保证答案唯一。

二、题解

思路：滑动窗口 + 频次数组。

1. 核心思路

题目要求在字符串 s 中寻找一个连续子串，因此可以使用滑动窗口。

使用两个指针维护窗口 [left, right]：

  • right 指针向右移动，不断扩大窗口。
  • 当窗口已经包含 t 中的全部字符时，移动 left 指针缩小窗口。
  • 在缩小窗口的过程中，记录长度最短的合法窗口。
  • 当窗口不再包含 t 的全部字符时，继续移动 right。

为了判断窗口是否包含 t 中的所有字符，使用数组 need 记录每个字符还需要多少个。

例如：

t = "AABC"

need['A'] = 2
need['B'] = 1
need['C'] = 1

同时使用 matched 记录当前窗口中已经成功匹配的字符数量。

当：

matched == t.length()

说明当前窗口已经包含了 t 中的全部字符。

2. 具体步骤

  1. 创建频次数组 need，统计字符串 t 中每个字符出现的次数。
  2. 定义左右指针 left 和 right，维护滑动窗口。
  3. 移动 right，将字符加入窗口：
    • 如果当前字符是窗口需要的字符，则让 matched 加一。
    • 将该字符对应的需求数量减一。
  4. 当 matched == t.length() 时，说明窗口已经满足要求：
    • 更新最短子串的起点和长度。
    • 移动 left，尝试缩小窗口。
  5. 当移除某个必要字符后，窗口不再满足要求，停止缩小窗口。
  6. 最后根据记录的起点和长度返回最短子串。

3. 关键逻辑

3.1 字符进入窗口

if (need[rightChar] > 0) {
    matched++;
}

need[rightChar]--;

在字符进入窗口之前，如果：

need[rightChar] > 0

说明当前窗口还缺少这个字符，因此该字符可以完成一次有效匹配，让 matched 加一。

无论这个字符是否是多余字符，都要执行：

need[rightChar]--;

表示窗口中增加了一个该字符。

例如：

t = "A"
s = "AA"

第一个 'A' 进入窗口时：

need['A'] = 1
matched = 1
need['A'] = 0

第二个 'A' 进入窗口时：

need['A'] = 0

此时这个 'A' 是多余的，因此 matched 不增加，随后：

need['A'] = -1

负数表示窗口中存在多余的该字符。

3.2 判断窗口是否合法

while (matched == t.length())

matched 记录的是成功匹配的字符总数，而不是字符种类数。

例如：

t = "AABC"

必须匹配：

A、A、B、C

一共四个字符，所以只有当：

matched == 4

窗口才满足要求。

3.3 字符离开窗口

need[leftChar]++;

if (need[leftChar] > 0) {
    matched--;
}

当左侧字符离开窗口时，需要恢复对该字符的需求，所以先执行：

need[leftChar]++;

如果增加后：

need[leftChar] > 0

说明窗口中缺少了一个必要字符，此时窗口不再合法，所以让 matched 减一。

如果增加后仍然小于或等于 0，说明移除的是一个多余字符，窗口仍然满足要求。

3.4 更新最短窗口

int currentLength = right - left + 1;

if (currentLength < minLength) {
    minLength = currentLength;
    minStart = left;
}

当窗口满足要求时，计算当前窗口长度。

如果当前窗口比之前记录的窗口更短，就更新：

  • 最短窗口的长度 minLength
  • 最短窗口的起点 minStart

最终通过下面的代码截取答案：

s.substring(minStart, minStart + minLength)

三、代码

class Solution {
    public String minWindow(String s, String t) {
        // 1. 处理特殊情况
        if (s == null || t == null || s.length() < t.length()) {
            return "";
        }

        /*
         * need[c] 表示当前窗口还需要多少个字符 c。
         * 题目中的字符为英文字母，因此使用长度为 128 的 ASCII 数组。
         */
        int[] need = new int[128];

        // 统计字符串 t 中每个字符出现的次数
        for (char c : t.toCharArray()) {
            need[c]++;
        }

        // 2. 定义变量
        int left = 0;

        // 当前窗口中已经成功匹配的字符数量
        int matched = 0;

        // 记录最短窗口的起点
        int minStart = 0;

        // 记录最短窗口的长度
        int minLength = Integer.MAX_VALUE;

        // 3. 核心逻辑：right 指针不断向右扩大窗口
        for (int right = 0; right < s.length(); right++) {
            char rightChar = s.charAt(right);

            /*
             * 如果当前字符是窗口还需要的字符，
             * 则成功匹配一个字符。
             */
            if (need[rightChar] > 0) {
                matched++;
            }

            // 当前字符进入窗口，需求数量减一
            need[rightChar]--;

            /*
             * 当窗口包含 t 中的全部字符时，
             * 尝试移动 left 缩小窗口。
             */
            while (matched == t.length()) {
                int currentLength = right - left + 1;

                // 更新最短窗口
                if (currentLength < minLength) {
                    minLength = currentLength;
                    minStart = left;
                }

                char leftChar = s.charAt(left);

                // leftChar 即将离开窗口，恢复对它的需求
                need[leftChar]++;

                /*
                 * 如果恢复后 need[leftChar] > 0，
                 * 说明窗口中缺少了一个必要字符。
                 */
                if (need[leftChar] > 0) {
                    matched--;
                }

                // 左指针向右移动，缩小窗口
                left++;
            }
        }

        // 4. 返回结果
        if (minLength == Integer.MAX_VALUE) {
            return "";
        }

        return s.substring(minStart, minStart + minLength);
    }
}

四、复杂度分析

时间复杂度：O(m+n)O(m + n)

说明：

  • m 是字符串 s 的长度。
  • n 是字符串 t 的长度。
  • 首先遍历一次 t，统计字符出现次数，时间复杂度为 O(n)O(n)。
  • left 和 right 指针都只会从左向右移动，不会回退，因此遍历 s 的总时间复杂度为 O(m)O(m)。
  • 总时间复杂度为 O(m+n)O(m + n)。

空间复杂度：O(1)O(1)

说明：

使用了长度固定为 128 的字符频次数组，空间大小不会随着输入规模的增大而变化，因此空间复杂度为 O(1)O(1)。

评论