题目描述

题目：最小覆盖子串

给定一个字符串 s 和一个字符串 t，找出 s 中包含 t 的所有字符的最小子串。如果 s 中不存在这样的子串，则返回空字符串。需要注意的是，t 中的字符不需要在 s 中以连续的顺序出现，但必须在 s 的子串中每个字符至少出现一次，且子串的长度要尽可能小。

示例 1:

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

示例 2:

输入: s = "abb", t = "abb"
输出: "abb"

示例 3:

输入: s = "ab", t = "ab"
输出: "ab"

示例 4:

输入: s = "axxxxyyyyb", t = "xyy"
输出: "xyyyb"

解题思路

为了找到包含 t 中所有字符的最小子串，我们可以使用滑动窗口和哈希表的方法。具体步骤如下：

1. 初始化：使用两个哈希表 need 和 window，其中 need 记录字符串 t 中每个字符需要的数量，window 记录当前窗口中每个字符的数量。同时，初始化窗口的左右指针 left 和 right 都指向字符串 s 的起始位置，以及两个变量 matched 来记录当前窗口中满足 t 条件的字符个数，和 result 来记录最小覆盖子串的起始位置和长度。

2. 移动右指针：不断移动右指针 right，扩大窗口，并更新 window 和 matched。如果 window 中某个字符的数量满足了 need 的要求，则 matched 加一。

3. 尝试移动左指针：当 matched 等于 t 的长度时，表示当前窗口已经包含了 t 的所有字符。此时尝试移动左指针 left 来缩小窗口，并更新 result（如果当前窗口大小小于 result 记录的大小）。在移动左指针的过程中，如果移除了 t 中需要的字符，则 matched 减一。

4. 重复步骤 2 和 3，直到右指针到达字符串 s 的末尾。

5. 返回结果：如果找到了满足条件的最小覆盖子串，则返回该子串；否则，返回空字符串。

PHP 代码示例

function minWindow($s, $t) {
    $need = array_count_values(str_split($t));
    $window = [];
    $left = $right = 0;
    $matched = 0;
    $result = ['start' => 0, 'len' => PHP_INT_MAX];

    while ($right < strlen($s)) {
        $c = $s[$right];
        if (isset($need[$c])) {
            $window[$c] = isset($window[$c]) ? $window[$c] + 1 : 1;
            if ($window[$c] == $need[$c]) {
                $matched++;
            }
        }
        $right++;

        // 尝试缩小窗口
        while ($matched == count($need)) {
            if ($right - $left < $result['len']) {
                $result = ['start' => $left, 'len' => $right - $left];
            }
            $d = $s[$left];
            $left++;
            if (isset($need[$d])) {
                if ($window[$d] == $need[$d]) {
                    $matched--;
                }
                $window[$d]--;
            }
        }
    }

    return $result['len'] == PHP_INT_MAX ? "" : substr($s, $result['start'], $result['len']);
}

Python 代码示例

def minWindow(s: str, t: str) -> str:
    need = collections.Counter(t)
    window = collections.defaultdict(int)
    left, right = 0, 0
    matched = 0
    result = float('inf'), None, None

    while right < len(s):
        c = s[right]
        if c in need:
            window[c] += 1
            if window[c] == need[c]:
                matched += 1
        right += 1

        while matched == len(need):
            if right - left < result[0]:
                result = (right - left, left, right)
            d = s[left]
            left += 1
            if d in need:
                if window[d] == need[d]:
                    matched -= 1
                window[d] -= 1

    return "" if result[1] is None else s[result[1]:result[2]]

JavaScript 代码示例

function minWindow(s, t) {
    const need = {};
    for (const char of t) {
        need[char] = (need[char] || 0) + 1;
    }
    let window = {};
    let left = 0, right = 0;
    let matched = 0;
    let result = [0, Infinity]; // [start, length]

    while (right < s.length) {
        const c = s[right];
        if (need[c]) {
            window[c] = (window[c] || 0) + 1;
            if (window[c] === need[c]) {
                matched++;
            }
        }
        right++;

        while (matched === Object.keys(need).length) {
            if (right - left < result[1]) {
                result = [left, right - left];
            }
            const d = s[left];
            left++;
            if (need[d]) {
                if (window[d] === need[d]) {
                    matched--;
                }
                window[d]--;
            }
        }
    }

    return result[1] === Infinity ? "" : s.substring(result[0], result[0] + result[1]);
}

希望这些示例能帮助你理解和解决“最小覆盖子串”的问题。