0076. Minimum Window Substring¶
题目信息¶
- 题号:
最小覆盖子串
- 难度:
Hard
- 主题:
字符串、滑动窗口、频次计数
- 原题:
- 重点:
从枚举所有子串,推导到维护字符缺口的线性滑动窗口
题目重述¶
给定字符串 s 和 t,寻找 s 中最短的连续子串,使该子串包含 t 中的全部字符,
并且每个字符的出现次数不少于其在 t 中的出现次数。字符区分大小写。
若不存在满足条件的子串,返回空字符串。约束为 1 <= s.length, t.length <= 10^5,两个字符串只包含英文字母。
自建示例¶
输入:s = "CABAA", t = "AABC"
输出:"CABA"
t 需要两个 A、一个 B 和一个 C。"CABA" 恰好满足全部频次,长度已经等于 t 的长度,
因此不可能存在更短答案。
输入:s = "ADOBECODEBANC", t = "ABC"
输出:"BANC"
窗口第一次覆盖 ABC 时仍然较长;继续移动左右边界后,最短覆盖窗口缩小为 "BANC"。
输入:s = "abc", t = "AA"
输出:""
s 中没有足够的 A,任何窗口都无法满足重复次数要求。
C++ 实现¶
#include <array>
#include <climits>
#include <string>
class Solution {
private:
static constexpr int ALPHABET = 128;
bool covers(const std::string& s,
int left,
int right,
const std::array<int, ALPHABET>& required) {
std::array<int, ALPHABET> count{};
for (int index = left; index <= right; ++index) {
unsigned char ch = static_cast<unsigned char>(s[index]);
++count[ch];
}
for (int ch = 0; ch < ALPHABET; ++ch) {
if (count[ch] < required[ch]) {
return false;
}
}
return true;
}
std::string bruteForce(const std::string& s,
const std::string& t) {
if (t.size() > s.size()) {
return "";
}
std::array<int, ALPHABET> required{};
for (char raw : t) {
unsigned char ch = static_cast<unsigned char>(raw);
++required[ch];
}
int bestStart = 0;
int bestLength = INT_MAX;
for (int left = 0; left < static_cast<int>(s.size()); ++left) {
for (int right = left;
right < static_cast<int>(s.size());
++right) {
int length = right - left + 1;
if (length >= bestLength) {
break;
}
if (covers(s, left, right, required)) {
bestStart = left;
bestLength = length;
break;
}
}
}
if (bestLength == INT_MAX) {
return "";
}
return s.substr(bestStart, bestLength);
}
std::string formedKinds(const std::string& s,
const std::string& t) {
if (t.size() > s.size()) {
return "";
}
std::array<int, ALPHABET> required{};
std::array<int, ALPHABET> window{};
int requiredKinds = 0;
for (char raw : t) {
unsigned char ch = static_cast<unsigned char>(raw);
if (++required[ch] == 1) {
++requiredKinds;
}
}
int formedKindsCount = 0;
int left = 0;
int bestStart = 0;
int bestLength = INT_MAX;
for (int right = 0;
right < static_cast<int>(s.size());
++right) {
unsigned char added = static_cast<unsigned char>(s[right]);
++window[added];
if (required[added] > 0 &&
window[added] == required[added]) {
++formedKindsCount;
}
while (formedKindsCount == requiredKinds) {
int length = right - left + 1;
if (length < bestLength) {
bestStart = left;
bestLength = length;
}
unsigned char removed =
static_cast<unsigned char>(s[left]);
++left;
if (required[removed] > 0 &&
window[removed] == required[removed]) {
--formedKindsCount;
}
--window[removed];
}
}
if (bestLength == INT_MAX) {
return "";
}
return s.substr(bestStart, bestLength);
}
std::string missingCount(const std::string& s,
const std::string& t) {
if (t.size() > s.size()) {
return "";
}
std::array<int, ALPHABET> need{};
for (char raw : t) {
unsigned char ch = static_cast<unsigned char>(raw);
++need[ch];
}
int missing = static_cast<int>(t.size());
int left = 0;
int bestStart = 0;
int bestLength = INT_MAX;
for (int right = 0;
right < static_cast<int>(s.size());
++right) {
unsigned char added = static_cast<unsigned char>(s[right]);
if (need[added] > 0) {
--missing;
}
--need[added];
while (missing == 0) {
int length = right - left + 1;
if (length < bestLength) {
bestStart = left;
bestLength = length;
}
unsigned char removed =
static_cast<unsigned char>(s[left]);
++left;
++need[removed];
if (need[removed] > 0) {
++missing;
}
}
}
if (bestLength == INT_MAX) {
return "";
}
return s.substr(bestStart, bestLength);
}
public:
std::string minWindow(std::string s, std::string t) {
return missingCount(s, t);
}
};
题解¶
暴力枚举¶
直接方法枚举每个左端点和右端点,再重新统计当前子串的字符频次。固定左端点后,第一个满足要求的右端点 已经给出该左端点对应的最短窗口,因此找到后可以停止继续扩张。
不同候选窗口大量重叠,重复统计使该方法最坏达到立方级。优化的关键是让窗口边界单调移动,并在加入或移出一个字符时增量更新状态。
窗口状态¶
窗口右端负责加入字符,左端负责移出字符。右端扩张到窗口可行后,继续扩张只会让窗口更长;此时应持续右移左端, 直到再移除一个字符就会破坏可行性。
这样,对于每个固定右端点,算法都会检查以该位置结尾的最短可行窗口。全局最短答案必然属于这些候选之一。
字符种类计数¶
一种直接状态是分别维护 required 和 window。当某种字符的窗口频次第一次达到需求频次时,
formedKindsCount 增加;当左端移除字符使该频次低于需求时,计数减少。
窗口有效当且仅当:
formedKindsCount == requiredKinds
这种写法清楚地区分“有多少种字符已经达标”,但需要两张频次数组和两个种类计数变量。
字符缺口计数¶
还可以让 need[ch] 同时表示需求与窗口余额。初始化时,它等于 t 中 ch 的数量;窗口加入字符后减一:
need[ch] > 0:窗口仍缺少该字符;need[ch] == 0:窗口恰好满足该字符需求;need[ch] < 0:窗口含有多余副本。
missing 记录所有字符副本的总缺口,初始为 t.length。加入字符前若 need[ch] > 0,
该字符填补了一个真实缺口,所以 missing 减一;多余副本不改变 missing。
窗口收缩¶
当 missing == 0 时,当前窗口已经覆盖 t。算法先提交当前长度,再移除左端字符:
++need[removed]
若更新后的 need[removed] > 0,窗口从满足需求变成缺少一个副本,missing 增加,收缩结束。
若值仍不大于 0,移除的只是多余副本,窗口仍然可行,可以继续缩短。
状态跟踪¶
以 s = "CABAA"、t = "AABC" 为例:
加入字符 |
关键余额 |
|
窗口状态 |
|---|---|---|---|
|
|
3 |
缺两个 A 和一个 B |
|
|
2 |
缺一个 A 和一个 B |
|
|
1 |
只缺一个 A |
|
|
0 |
|
此时移除左端 C 后,need['C'] 重新变为正数,窗口立即失效。因此 CABA 是该右端点对应的最短可行窗口。
复杂度¶
暴力方法最坏时间为 O(|s|^3)。两种滑动窗口方法中,左右指针都只单调经过 s 一次,
初始化需求需要 O(|t|),总时间为 O(|s| + |t|)。
英文字母属于固定大小字符集,频次数组占用常量空间;除返回字符串外,额外空间为 O(1)。