HHot 100C++ 图解

76. 最小覆盖子串

困难 子串 / 前缀和 4 帧动画 在力扣上做

一句话套路滑窗 + need/window 计数,先扩后缩

题目描述

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

测试用例保证答案唯一。

 

示例 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 的子串中,
因此没有符合条件的子字符串,返回空字符串。

 

提示:

  • m == s.length
  • n == t.length
  • 1 <= m, n <= 105
  • s 和 t 由英文字母组成

 

进阶:你能设计一个在 O(m + n) 时间内解决此问题的算法吗?

思路

时间O(|s| + |t|)
空间O(字符集)

思路

变长窗口的标准模板 —— 右扩到「合法」,再左缩到「不合法」,在每次合法的时刻记录答案。

用一个 required 计数器(还差多少个字符),避免每步比较整个计数数组。

技巧

cnt[c] 表示「c 还缺几个」。--cnt[c] >= 0 说明这次拿到的正是还缺的那个(注意是>= 0,不是 > 0:补上最后一个缺口时,自减后恰好是 0)。出窗时用反方向的 > 0。

图解

c 0 a 1 b 2 w 3 e 4 f 5 g 6 e 7 w 8 c 9 w 10 a 11 e 12 f 13 g 14 c 15 f 16
字符串 cabwefgewcwaefgcf(来自本仓库测试数据,下标从 0 开始)

逐帧动画

1 / 4

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/04_substring.cpp24 行
namespace lc0076 {
class Solution {
 public:
  string minWindow(string s, string t) {
    if (t.empty() || s.size() < t.size()) return "";  // 空 t 直接返回,不等 `required` 变负后才「碰巧」正确
    int cnt[256] = {};  // 按 unsigned char 全值域开,128 会在高字节上越界
    for (char c : t) ++cnt[(unsigned char)c];
    int required = (int)t.size();  // 还差多少个(含重复)字符
    int bestL = 0, bestLen = INT_MAX, l = 0;
    for (int r = 0; r < (int)s.size(); ++r) {
      if (--cnt[(unsigned char)s[r]] >= 0) --required;  // 这个字符是需要的
      while (required == 0) {                            // 窗口已覆盖 t
        if (r - l + 1 < bestLen) {
          bestLen = r - l + 1;
          bestL = l;
        }
        if (++cnt[(unsigned char)s[l]] > 0) ++required;  // 移出后重新缺了
        ++l;
      }
    }
    return bestLen == INT_MAX ? "" : s.substr(bestL, bestLen);
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q76_minimum_window_substring7 行
lc0076::Solution s;
CHECK_EQ(s.minWindow("ADOBECODEBANC", "ABC"), string("BANC"));
CHECK_EQ(s.minWindow("a", "a"), string("a"));
CHECK_EQ(s.minWindow("a", "aa"), string(""));   // t 有重复,s 不够
CHECK_EQ(s.minWindow("aa", "aa"), string("aa"));
CHECK_EQ(s.minWindow("cabwefgewcwaefgcf", "cae"), string("cwae"));
CHECK_EQ(s.minWindow("abc", ""), string(""));      // 空 t 显式返回空串

↑↓ 选择↵ 打开/ 随时唤起