#LC76. 最小覆盖子串

最小覆盖子串

LeetCode76这道题是 “滑动窗口” (Sliding Window) 算法的教科书级例题，非常适合训练学生对双指针的运用以及对时间复杂度的敏感度。

Part 1. 题目描述

题目名称：最小覆盖子串 (Minimum Window Substring)

【题目描述】

给定两个字符串 SS 和 TT。请在字符串 SS 中找出包含 TT 中所有字符（包括重复字符）的最小子串。 如果 SS 中不存在覆盖 TT 中所有字符的子串，则输出空字符串（在输出中体现为不输出任何内容并换行）。 如果存在多个符合条件的最小长度子串，返回 SS 中出现位置最早的那个（原题隐含逻辑，通常题目需明确唯一性或任意性，这里按原题逻辑只需输出找到的那个）。

注意：

  • 对于 TT 中重复出现的字符，在子串中也必须包含同样数量（或更多）的该字符。
  • 子串必须是连续的。

【输入格式】

输入共两行： 第一行包含一个字符串 SS。 第二行包含一个字符串 TT。 （字符串仅包含英文字母，长度不超过 10510^5）

【输出格式】

输出共一行，表示满足条件的最小子串。如果不存这样的子串，输出空行。

【样例 1】

输入：

ADOBECODEBANC
ABC

输出：

BANC

说明： 最小覆盖子串 "BANC" 包含 A, B, C。虽然 "ADOBEC" 也包含，但长度为 6，"BANC" 长度为 4，故选 "BANC"。

【样例 2】

输入：

a
a

输出：

a

【样例 3】

输入：

a
aa

输出：

说明： TT 需要两个 'a'，而 SS 只有一个，无法覆盖，输出空。

【数据范围与提示】

对于 100%100\% 的数据，满足：

  • 1≤∣T∣≤∣S∣≤1051 \le |T| \le |S| \le 10^5
  • 字符串由大小写英文字母组成。
  • 时间限制：1.0s
  • 空间限制：128MB

Part 2. 教练指导：解题思路与启发

1. 预备知识点

在解决这道题之前，你需要掌握：

  • 哈希表 / 桶计数：利用数组 cnt[128] 快速记录字符出现的频次（ASCII 码映射）。
  • 双指针 (Two Pointers)：利用两个指针维护一个动态区间。
  • 滑动窗口 (Sliding Window)：双指针的一种特殊形态，一伸一缩，像尺取法一样寻找最优解。

2. 读题关键词

看到这些词，你的 DNA 里应该反应出“滑动窗口”：

  • “最小 / 最短”：暗示我们需要寻找极值。
  • “子串”：强调连续性，适合双指针。
  • “覆盖所有字符”：涉及字符计数和状态校验。

3. 启发式教学：草稿纸上的推演

同学们，拿出草稿纸，我们画图来模拟这个过程。

核心策略： 我们需要两个指针 left（左边界）和 right（右边界）。

  1. 扩张阶段：移动 right，像吃豆人一样吃进字符，直到窗口里的字符能凑齐一个 TT。
  2. 收缩阶段：一旦窗口“合法”（凑齐了），我们就尝试移动 left，把多余的字符吐出来，让窗口尽可能小，同时更新最小长度记录。
  3. 循环：如果吐多了导致不合法，就重新回到扩张阶段。

草稿演示（以 S="ADOBECODEBANC", T="ABC" 为例）：

  • Step 1 (准备): 统计 T：A:1, B:1, C:1。记 need_count = 3。
  • Step 2 (R 右移):
    • R 扫过 "ADOBEC"：
    • 遇到 A，需要！need_count 变 2。
    • 遇到 B，需要！need_count 变 1。
    • 遇到 C，需要！need_count 变 0。
    • 停！ 此时 Window="ADOBEC"，合法。当前 MinLen=6。
  • Step 3 (L 左移):
    • L 指向 'A'。尝试删掉 'A'？
    • 不行！'A' 是必须的。如果删了，need_count 变回 1，窗口不合法。
    • 记录当前答案 "ADOBEC"。
    • 为了找更小的，我们必须忍痛删掉 'A'，L 右移，need_count=1。
  • Step 4 (R 继续右移):
    • 寻找下一个能弥补 'A' 的字符... 一直向右找...
    • 直到遇到最后的 'A'。Window 再次合法。
    • 再次尝试 L 收缩，把左边没用的 'D', 'O', 'B', 'E'... 都吐出来。
    • 最终找到 "BANC"。

4. 复杂度分析

  • 时间复杂度：O(∣S∣+∣T∣)O(|S| + |T|)。
    • 虽然有两层循环（while 里面套 while），但注意：left 和 right 指针都只会从 0 走到 N，每个字符最多被访问两次（进窗一次，出窗一次）。绝对不是 O(N2)O(N^2)。
  • 空间复杂度：O(C)O(C)，其中 CC 是字符集大小（128）。我们只需要一个数组来存计数。

Part 3. NOI 风格参考代码 (C++14)

/**
 * 题目名称：最小覆盖子串
 * 算法核心：滑动窗口 (Sliding Window)
 * 编写风格：NOI/NOIP C++14 标准
 */

#include <iostream>
#include <vector>
#include <string>
#include <climits>
#include <cstdio>

using namespace std;

// 字符集大小，ASCII 码覆盖 0-127 即可
const int MAX_CHAR = 128;

int main() {
    // 提升 cin/cout 效率，NOI 常用技巧
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s, t;
    // 读入两行字符串
    if (!(cin >> s >> t)) return 0;

    // 统计 T 中每个字符的需求量
    // need[c] > 0 表示还需要字符 c 的数量
    // need[c] < 0 表示窗口里多出来的字符 c 的数量
    vector<int> need(MAX_CHAR, 0);
    for (char c : t) {
        need[c]++;
    }

    int need_cnt = t.length(); // 还需要凑齐的总字符数
    int min_len = INT_MAX;     // 记录最小长度
    int start_pos = 0;         // 记录最小子串的起始位置

    int left = 0, right = 0;
    int n = s.length();

    // 开始滑动窗口
    while (right < n) {
        char c_in = s[right];
        
        // 如果当前字符是 T 需要的，need_cnt 减 1
        if (need[c_in] > 0) {
            need_cnt--;
        }
        // 无论是不是需要的，都要在计数表中减去（入窗）
        // 如果 need[c] 变成负数，说明窗口里这个字符多了
        need[c_in]--;
        right++;

        // 当 need_cnt == 0 时，说明窗口已包含 T 中所有字符（合法窗口）
        // 尝试收缩左边界
        while (need_cnt == 0) {
            int current_len = right - left;
            
            // 更新最小覆盖子串的信息
            if (current_len < min_len) {
                min_len = current_len;
                start_pos = left;
            }

            char c_out = s[left];
            // 准备将 c_out 移出窗口
            need[c_out]++; // 恢复计数

            // 如果恢复后 need[c_out] > 0，说明刚才移出的是一个必须字符
            // 窗口不再合法，need_cnt 增加，循环将终止，继续由 right 扩张
            if (need[c_out] > 0) {
                need_cnt++;
            }
            
            left++;
        }
    }

    // 输出结果
    if (min_len == INT_MAX) {
        cout << "" << endl; // 未找到
    } else {
        cout << s.substr(start_pos, min_len) << endl;
    }

    return 0;
}

代码易错点注释：

  1. need[c_in] > 0 判断：一定要在 need[c_in]-- 之前判断。因为如果 need 已经是负数（说明多余了），再遇到这个字符并不能减少 need_cnt。
  2. right++ 的位置：通常习惯 s[right++]，但在计算长度 right - left 时要注意 right 此时已经指向下一个位置了，所以长度不需要 +1。
  3. 空串处理：如果循环结束后 min_len 仍为 INT_MAX，说明无解。

Part 4. 数据生成器 (C++)

为了训练和测试，我们需要一个能够生成各种边界情况的数据生成器。以下代码会生成 10 组 x.in 和 x.out 文件。

#include <iostream>
#include <vector>
#include <string>
#include <climits>
#include <random>
#include <fstream>
#include <algorithm>
#include <chrono>

using namespace std;

// ==========================================
// Part 1: 题解函数 (Solver) - 用于生成 .out
// ==========================================
string solve(string s, string t) {
    if (s.empty() || t.empty()) return "";
    vector<int> map(128, 0);
    for (char c : t) map[c]++;
    
    int counter = t.size();
    int begin = 0, end = 0;
    int d = INT_MAX;
    int head = 0;
    
    while (end < s.size()) {
        if (map[s[end]] > 0) {
            counter--;
        }
        map[s[end]]--;
        end++;
        
        while (counter == 0) {
            if (end - begin < d) {
                d = end - begin;
                head = begin;
            }
            map[s[begin]]++;
            if (map[s[begin]] > 0) {
                counter++;
            }
            begin++;
        }
    }
    return d == INT_MAX ? "" : s.substr(head, d);
}

// ==========================================
// Part 2: 数据生成策略
// ==========================================
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

char rand_char() {
    // 随机生成大小写字母
    int r = rng() % 52;
    if (r < 26) return 'a' + r;
    else return 'A' + (r - 26);
}

string rand_string(int len) {
    string res = "";
    for (int i = 0; i < len; i++) res += rand_char();
    return res;
}

// 确保 s 包含 t 的构造函数（保证有解）
string make_solvable_string(int s_len, string t) {
    string s = rand_string(s_len - t.length());
    // 将 t 插入到 s 的随机位置，或者打散插入
    // 这里采用简单策略：先生成随机串，然后随机替换其中的字符为 t 的字符
    // 为了保证子串的随机性，我们直接把 t 的字符随机撒进 s 中
    string full_s = s + t; 
    shuffle(full_s.begin(), full_s.end(), rng);
    return full_s;
}

void generate_case(int id, string& s, string& t) {
    int max_n = 100000;
    
    switch(id) {
        case 1: // 题目样例
            s = "ADOBECODEBANC";
            t = "ABC";
            break;
        case 2: // 长度相等，就是自身
            s = "Algorithm";
            t = "Algorithm";
            break;
        case 3: // T 比 S 长 (无解)
            s = "short";
            t = "longerstring";
            break;
        case 4: // S 不包含 T 的所有字符 (无解)
            s = "AABBCC";
            t = "ABCDE";
            break;
        case 5: // T 有重复字符
            s = "aaabbbccc";
            t = "abcabc";
            break;
        case 6: // 小规模随机 (有解/无解随机)
            t = rand_string(5);
            s = rand_string(20);
            break;
        case 7: // 中规模随机，T 是 S 的子串
            t = rand_string(50);
            s = make_solvable_string(1000, t);
            break;
        case 8: // 大规模，T 很短，S 很长 (测试大量无用字符)
            t = "ABC";
            s = rand_string(max_n); 
            // 强行插入 ABC 保证有解
            s[max_n/2] = 'A'; s[max_n/2+100] = 'B'; s[max_n/2+200] = 'C';
            break;
        case 9: // 大规模，T 很长
            t = rand_string(1000);
            s = make_solvable_string(max_n, t);
            break;
        case 10: // 极限数据，最坏情况
            // 全是同一个字符，退化测试
            t = string(100, 'A');
            s = string(max_n, 'A');
            break;
    }
}

int main() {
    printf("Generating data...\n");
    for (int i = 1; i <= 10; i++) {
        string s, t;
        generate_case(i, s, t);
        
        // 写入 .in
        string in_name = to_string(i) + ".in";
        ofstream fin(in_name);
        fin << s << "\n" << t << "\n";
        fin.close();
        
        // 计算并写入 .out
        string out_name = to_string(i) + ".out";
        ofstream fout(out_name);
        string ans = solve(s, t);
        if (!ans.empty()) fout << ans << "\n"; // 如果有答案输出
        else fout << "\n"; // 空答案输出空行
        fout.close();
        
        printf("Generated Case %d: |S|=%lu, |T|=%lu\n", i, s.length(), t.length());
    }
    printf("Done.\n");
    return 0;
}

测试点覆盖说明

  • Case 1: 官方样例，确保理解一致。
  • Case 2: ∣S∣=∣T∣|S|=|T|，边界测试。
  • Case 3-4: 无解的情况（长度不够或字符缺失）。
  • Case 5: TT 中包含重复字符，测试计数逻辑。
  • Case 6-9: 不同规模的随机数据，覆盖 N=103N=10^3 到 10510^5。
  • Case 10: 极端同字符情况，测试逻辑是否退化为 O(N)O(N)。
  1. Language
  2. 兼容模式
  3. 主题
  3. Worker 0, 25ms
  4. Powered by Hydro v5.0.0-beta.8 Community