yicong@algo: ~/code/04-substring/0076-minimum-window-substring.cpp

yicong@algo:~/code/04-substring$ cat 0076-minimum-window-substring.cpp

76. 最小覆盖子串

困难 子串 题目 ↗ 源码 ↗

// 思路

答案窗口的两个端点一定都是 t 里的字符——否则把端点内缩一格仍然覆盖 t,窗口还能更短。 所以只需要处理 s 中属于 t 的字符,其它字符直接跳过。 版本一(你的写法)用「字符 -> 位置列表」记录窗口,每次比对都要扫一遍字符表; 版本二用 formed 计数器把「是否覆盖 t」的判断降到 O(1),时间降到 O(|s|)。

// 时间复杂度

版本一:O(|s| · K),K 是 t 里不同字符的种数(≤ 52) 版本二:O(|s| + |t|),right 和 left 各自最多走完 s 一遍

// 空间复杂度

版本一:O(|s|),window 里存的是窗口内每个字符的位置列表 版本二:O(1),只有 128 的定长表

// 易错点

1. covered 要遍历 ts,而不是遍历 window —— window 里可能压根没出现过 t 的某个字符, 只扫 window 会把"缺字符"误判成"覆盖了"。 2. 版本二里 formed 只在"数量刚好追平"的那一次加一,所以判断是 cnt[in] == need[in]。 写成 cnt[in] >= need[in] 会在同一个字符上反复累加,formed 虚高。 3. 出窗时必须"先比后减":先看 cnt[out] == need[out],再把 cnt[out] 减一。 顺序反了,就永远比不到"刚好够"的那一次,formed 会少减。 4. 版本一记录答案后要删最靠前的字符,删完不一定还覆盖,判定要用 while 而不是 if。 5. 只记长度不够,必须同时记起点 start,否则最后没法 substr。

// 面试口述要点

1. 用双指针在 s 上维护一个窗口,让窗口内包含 t 的全部字符(提示 1); 2. right 右移扩张,直到窗口恰好覆盖 t(提示 2); 3. 一旦覆盖,就左移 left 收缩,每收缩一步都记一次长度,直到刚好不再覆盖(提示 3); 4. right 继续右移,重复直到 right 走到 s 末尾(提示 4)。 讲完再补一句:用 formed 计数器替代逐字符比对,把"是否覆盖"从 O(K) 降到 O(1)。

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // ================================================================
    // 版本一:字符 -> 位置列表(你的写法)
    //   ts       : t 的哈希表,字符 -> 需要几个
    //   window   : 当前窗口的哈希表,字符 -> 它在 s 中出现的位置(位置递增压入)
    //   covered  : 窗口里每种字符的个数是否都已达到 ts 的要求
    //   leftmost : 窗口最靠前的位置,也就是当前窗口的左端点
    // 每读到一个 t 里的字符就压进 window;只要 covered,说明窗口刚好覆盖 t,
    // 记下长度,然后删掉"最靠前位置"的那个字符,把窗口往右缩一格,再判定一次。
    // ================================================================
    string minWindow(string s, string t) {
        unordered_map<char, int> ts;                 // t 的哈希表:字符 -> 需要几个
        for (char c : t) ts[c]++;

        unordered_map<char, vector<int>> window;     // 当前窗口:字符 -> 它出现的位置(递增)
        int minlength = INT_MAX;                     // 最小覆盖子串的长度
        int start = 0;                               // 最小覆盖子串的起点
        string ans = "";

        // 窗口是否已经覆盖 t 的全部字符和个数
        auto covered = [&]() -> bool {
            for (auto& p : ts) {
                auto it = window.find(p.first);
                if (it == window.end() || (int)it->second.size() < p.second) return false;
            }
            return true;
        };

        // 窗口最靠前的字符及其位置
        auto leftmost = [&]() -> pair<char, int> {
            pair<char, int> res = {0, INT_MAX};
            for (auto& p : window)
                if (!p.second.empty() && p.second.front() < res.second) res = {p.first, p.second.front()};
            return res;
        };

        for (int right = 0; right < (int)s.size(); right++) {
            if (!ts.count(s[right])) continue;       // 不是 t 里的字符,不进窗口
            window[s[right]].push_back(right);       // 压入当前位置

            while (covered()) {                      // 一致:记下长度,然后删掉最靠前位置的字符
                auto [leftChar, leftPos] = leftmost();
                int len = right - leftPos + 1;
                if (len < minlength) {
                    minlength = len;
                    start = leftPos;
                }
                window[leftChar].erase(window[leftChar].begin());
            }
        }

        if (minlength == INT_MAX) return ans;
        return s.substr(start, minlength);
    }

    // ================================================================
    // 版本二:数组 + formed 计数器,O(|s|),面试写的版本(对应上面 4 条提示)
    //   need[c]  : t 里字符 c 需要几个
    //   cnt[c]   : 当前窗口里字符 c 有几个
    //   required : t 里有多少种不同字符
    //   formed   : 已经"凑够数量"的字符种数
    // formed == required 等价于"窗口覆盖了 t",O(1) 就能判断,不用扫字符表。
    // 非 t 字符的 need 是 0,进窗/出窗时被 need[c] > 0 挡住,cnt 不动,
    // 所以不需要像版本一那样显式过滤,它们天然对 formed 没有影响。
    // 字符统一用 int 变量接住再当下标:题目保证 s 和 t 只含英文字母,
    // ASCII 码都落在 0~127,用 int 接一下既不会越界,也不会触发 gcc 的
    // -Wchar-subscripts 警告(char 在某些平台是有符号的,编译器会担心下标为负)。
    // ================================================================
    string minWindow_v2(string s, string t) {
        // need[c] = t 里字符 c 需要几个
        int need[128] = {0};
        for (int i = 0; i < (int)t.size(); i++) {
            int c = t[i];
            need[c]++;
        }

        // required = t 里有几种不同的字符
        int required = 0;
        for (int c = 0; c < 128; c++) {
            if (need[c] > 0) {
                required++;
            }
        }

        int cnt[128] = {0};                          // cnt[c] = 当前窗口里字符 c 有几个
        int formed = 0;                              // 窗口里"数量已经够了"的字符有几种
        int left = 0;                                // 窗口左端点
        int start = 0;                               // 答案的起点
        int minlength = INT_MAX;                     // 答案的长度

        for (int right = 0; right < (int)s.size(); right++) {
            // ---------- 第 1 步:right 位置的字符进窗 ----------
            // 提示 2:right 右移扩张,直到窗口覆盖 t
            int in = s[right];
            if (need[in] > 0) {                      // 不是 t 里的字符,不参与统计
                cnt[in]++;
                if (cnt[in] == need[in]) {           // 这个字符的数量刚好够了
                    formed++;
                }
            }

            // ---------- 第 2 步:窗口已经覆盖 t,就把 left 往右推,尽量缩短 ----------
            // 提示 3:边收缩边记长度,直到刚好不再覆盖
            while (formed == required) {
                int len = right - left + 1;
                if (len < minlength) {               // 记下更短的答案
                    minlength = len;
                    start = left;
                }

                int out = s[left];                   // left 位置的字符出窗
                if (need[out] > 0) {
                    if (cnt[out] == need[out]) {     // 它现在刚好够,出去就不够了
                        formed--;
                    }
                    cnt[out]--;
                }
                left++;
            }
            // 提示 4:left 收缩到不再覆盖后,right 继续右移,直到 s 末尾
        }

        // ---------- 第 3 步:一次都没有覆盖成功过 ----------
        if (minlength == INT_MAX) {
            return "";
        }
        return s.substr(start, minlength);
    }
};

// 本地测试:输入两个字符串 s 和 t;输出最小覆盖子串,不存在则输出 none
// 同时跑两个版本并比对结果,方便验证优化版和原版等价
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s, t;
    if (!(cin >> s >> t)) return 0;

    string ans1 = Solution().minWindow(s, t);
    string ans2 = Solution().minWindow_v2(s, t);

    if (ans1 != ans2) {
        cout << "MISMATCH: v1=" << (ans1.empty() ? "none" : ans1)
             << " v2=" << (ans2.empty() ? "none" : ans2) << '\n';
        return 0;
    }
    if (ans1.empty()) {
        cout << "none\n";
    } else {
        cout << ans1 << '\n';
    }
    return 0;
}