跳到主要内容

LeetCode 76. 最小覆盖子串

本节目标

用需求频次、窗口频次和满足种类数寻找覆盖目标字符串的最短子串。

这道题放在数组与矩阵综合中，因为它把频次表与最短窗口的收缩策略组合起来。窗口必须覆盖 t 中每种字符的指定次数，而不只是出现过这些字符。

查看原题

题意与约束​

给定字符串 s 与 t，返回 s 中包含 t 所有字符及其数量的最短子串。若不存在，返回空字符串；若有多个最短解，题目保证答案唯一。

例如 t 为 AABC 时，窗口需要至少包含两个 A、一个 B 和一个 C。因此仅用集合记录字符是否出现不够。

从枚举子串到维护频次​

最直接的办法是枚举 s 的所有连续子串，再统计每个候选的字符频次并与 t 的需求比较。候选区间有 O(|s|²) 个；若每次重新计数，最坏时间会达到 O(|s|³ + |t|)。即使对同一起点增量统计，将复杂度降到 O(|s|² + |t|)，更换起点后仍会重复计算大量重叠区间。

窗口右移时实际只加入一个字符，左移时也只移除一个字符。若同时维护窗口频次和已经满足需求的字符种类数，就能在常数级更新后判断当前区间是否可行，让两个边界都只向右移动。

用 formed 表示窗口是否可行​

先用 need 统计目标频次，required 是需求中不同字符的种类数。窗口右端加入字符后，只有该字符属于 need 才更新窗口计数；当它的计数首次达到需求时，formed 加一。

当 formed 等于 required 时，每种需求字符的频次都已满足，窗口可行。此时先尝试更新最短答案，再移除左端字符；若移出的字符刚好使某种频次低于需求，formed 减一，窗口重新变为不可行。

代码实现​

两份源码都只为目标中出现的字符维护窗口频次，避免无关字符干扰 formed。更新最优答案发生在左端移出前，保证记录的窗口仍覆盖整个目标。

C++17
#include <climits>
#include <string>
#include <unordered_map>
using namespace std;

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> need;
        unordered_map<char, int> window;
        for (char ch : t) {
            need[ch]++;
        }

        int required = static_cast<int>(need.size());
        int formed = 0;
        int left = 0;
        int bestStart = 0;
        int bestLength = INT_MAX;

        for (int right = 0; right < static_cast<int>(s.size()); right++) {
            char ch = s[right];
            if (need.count(ch) > 0) {
                window[ch]++;
                if (window[ch] == need[ch]) {
                    formed++;
                }
            }

            // 已覆盖所有需求时，尽可能移除左侧冗余字符。
            while (formed == required) {
                if (right - left + 1 < bestLength) {
                    bestStart = left;
                    bestLength = right - left + 1;
                }
                char leftChar = s[left];
                if (need.count(leftChar) > 0) {
                    if (window[leftChar] == need[leftChar]) {
                        formed--;
                    }
                    window[leftChar]--;
                }
                left++;
            }
        }
        return bestLength == INT_MAX ? "" : s.substr(bestStart, bestLength);
    }
};

复杂度分析​

  • 时间复杂度：O(|s| + |t|)。两个边界都只向右移动，目标频次只统计一次。
  • 空间复杂度：O(|Σ|)，其中 Σ 是需要维护频次的字符集合。

易错点​

  • 把 formed 记成已匹配字符总数；它应统计已达到目标频次的字符种类数。
  • 左端移出需求字符时，先减少频次再判断是否破坏满足条件，容易漏掉临界值。
  • 只判断每个字符出现过，无法处理目标含重复字符的情况。

模式迁移​

它是滑动窗口解题框架中最短可行窗口的频次版：将窗口和达到阈值替换为所有需求频次均满足。类似结构可用于最短包含若干类别、最短覆盖多重集合等问题。