朝花夕拾

最小覆盖子串

4 min read

题目描述

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

注意：

  • 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
  • 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1： 输入：s = “ADOBECODEBANC”, t = “ABC”
输出：“BANC”
解释：最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、‘B’ 和 ‘C’。

示例 2： 输入：s = “a”, t = “a”
输出：“a”
解释：整个字符串 s 是最小覆盖子串。

示例 3:
输入: s = “a”, t = “aa”
输出: ""
解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中， 因此没有符合条件的子字符串，返回空字符串。

思路&js代码

1、滑动窗口

function isCovered(cntS, cntT) {
    for (let i = 'A'.charCodeAt(0); i <= 'Z'.charCodeAt(0); i++) {
        if (cntS[i] < cntT[i]) {
            return false;
        }
    }
    for (let i = 'a'.charCodeAt(0); i <= 'z'.charCodeAt(0); i++) {
        if (cntS[i] < cntT[i]) {
            return false;
        }
    }
    return true;
}
 
var minWindow = function(s, t) {
    const cntS = Array(128).fill(0); // s 子串字母的出现次数
    const cntT = Array(128).fill(0); // t 中字母的出现次数
    for (const c of t) {
        cntT[c.codePointAt(0)]++;
    }
 
    const m = s.length;
    let ansLeft = -1, ansRight = m;
    let left = 0;
    for (let right = 0; right < m; right++) { // 移动子串右端点
        cntS[s[right].codePointAt(0)]++; // 右端点字母移入子串
        while (isCovered(cntS, cntT)) { // 涵盖
            if (right - left < ansRight - ansLeft) { // 找到更短的子串
                ansLeft = left; // 记录此时的左右端点
                ansRight = right;
            }
            cntS[s[left].codePointAt(0)]--; // 左端点字母移出子串
            left++;
        }
    }
    return ansLeft < 0 ? "" : s.substring(ansLeft, ansRight + 1);
};

2、优化

var minWindow = function(s, t) {
    const cnt = Array(128).fill(0);
    let less = 0;
    for (let c of t) {
        c = c.codePointAt(0);
        if (cnt[c] === 0) {
            less++; // 有 less 种字母的出现次数 < t 中的字母出现次数
        }
        cnt[c]++;
    }
 
    const m = s.length;
    let ansLeft = -1, ansRight = m;
    let left = 0;
    for (let right = 0; right < m; right++) { // 移动子串右端点
        const c = s[right].codePointAt(0); // 右端点字母
        cnt[c]--; // 右端点字母移入子串
        if (cnt[c] === 0) {
            // 原来窗口内 c 的出现次数比 t 的少，现在一样多
            less--;
        }
        while (less === 0) { // 涵盖：所有字母的出现次数都是 >=
            if (right - left < ansRight - ansLeft) { // 找到更短的子串
                ansLeft = left; // 记录此时的左右端点
                ansRight = right;
            }
            const x = s[left].codePointAt(0); // 左端点字母
            if (cnt[x] === 0) {
                // x 移出窗口之前，检查出现次数，
                // 如果窗口内 x 的出现次数和 t 一样，
                // 那么 x 移出窗口后，窗口内 x 的出现次数比 t 的少
                less++;
            }
            cnt[x]++; // 左端点字母移出子串
            left++;
        }
    }
    return ansLeft < 0 ? "" : s.substring(ansLeft, ansRight + 1);
};

Graph View