0076. Minimum Window Substring ============================== 题目信息 -------- :题号: 0076. 最小覆盖子串 :难度: Hard :主题: 字符串、滑动窗口、频次计数 :原题: `LeetCode 0076 `_ :重点: 从枚举所有子串,推导到维护字符缺口的线性滑动窗口 题目重述 -------- 给定字符串 ``s`` 和 ``t``,寻找 ``s`` 中最短的连续子串,使该子串包含 ``t`` 中的全部字符, 并且每个字符的出现次数不少于其在 ``t`` 中的出现次数。字符区分大小写。 若不存在满足条件的子串,返回空字符串。约束为 ``1 <= s.length, t.length <= 10^5``,两个字符串只包含英文字母。 自建示例 -------- .. code-block:: text 输入:s = "CABAA", t = "AABC" 输出:"CABA" ``t`` 需要两个 ``A``、一个 ``B`` 和一个 ``C``。``"CABA"`` 恰好满足全部频次,长度已经等于 ``t`` 的长度, 因此不可能存在更短答案。 .. code-block:: text 输入:s = "ADOBECODEBANC", t = "ABC" 输出:"BANC" 窗口第一次覆盖 ``ABC`` 时仍然较长;继续移动左右边界后,最短覆盖窗口缩小为 ``"BANC"``。 .. code-block:: text 输入:s = "abc", t = "AA" 输出:"" ``s`` 中没有足够的 ``A``,任何窗口都无法满足重复次数要求。 C++ 实现 -------- .. code-block:: cpp #include #include #include class Solution { private: static constexpr int ALPHABET = 128; bool covers(const std::string& s, int left, int right, const std::array& required) { std::array count{}; for (int index = left; index <= right; ++index) { unsigned char ch = static_cast(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 required{}; for (char raw : t) { unsigned char ch = static_cast(raw); ++required[ch]; } int bestStart = 0; int bestLength = INT_MAX; for (int left = 0; left < static_cast(s.size()); ++left) { for (int right = left; right < static_cast(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 required{}; std::array window{}; int requiredKinds = 0; for (char raw : t) { unsigned char ch = static_cast(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(s.size()); ++right) { unsigned char added = static_cast(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(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 need{}; for (char raw : t) { unsigned char ch = static_cast(raw); ++need[ch]; } int missing = static_cast(t.size()); int left = 0; int bestStart = 0; int bestLength = INT_MAX; for (int right = 0; right < static_cast(s.size()); ++right) { unsigned char added = static_cast(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(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`` 增加;当左端移除字符使该频次低于需求时,计数减少。 窗口有效当且仅当: .. code-block:: text 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``。算法先提交当前长度,再移除左端字符: .. code-block:: text ++need[removed] 若更新后的 ``need[removed] > 0``,窗口从满足需求变成缺少一个副本,``missing`` 增加,收缩结束。 若值仍不大于 0,移除的只是多余副本,窗口仍然可行,可以继续缩短。 状态跟踪 ~~~~~~~~ 以 ``s = "CABAA"``、``t = "AABC"`` 为例: .. list-table:: :header-rows: 1 * - 加入字符 - 关键余额 - ``missing`` - 窗口状态 * - ``C`` - ``C: 0`` - 3 - 缺两个 A 和一个 B * - ``A`` - ``A: 1`` - 2 - 缺一个 A 和一个 B * - ``B`` - ``B: 0`` - 1 - 只缺一个 A * - ``A`` - ``A: 0`` - 0 - ``CABA`` 可行 此时移除左端 ``C`` 后,``need['C']`` 重新变为正数,窗口立即失效。因此 ``CABA`` 是该右端点对应的最短可行窗口。 复杂度 ~~~~~~ 暴力方法最坏时间为 ``O(|s|^3)``。两种滑动窗口方法中,左右指针都只单调经过 ``s`` 一次, 初始化需求需要 ``O(|t|)``,总时间为 ``O(|s| + |t|)``。 英文字母属于固定大小字符集,频次数组占用常量空间;除返回字符串外,额外空间为 ``O(1)``。