题意概括

给定两个字符串 s 和 t，要求在字符串 s 中找出最短的一个连续子串，这个子串必须包含字符串 t 中的所有字符，并且 t 中各字符出现的次数也必须得到满足。如果 s 中不存在这样的子串，则返回一个空字符串。

题目说明:

• t 中的重复字符也需要被计算在内。
• 如果存在答案，题目保证答案是唯一的。

基础知识

本题是 滑动窗口 (Sliding Window) 算法的一道经典应用题。滑动窗口算法通常用于解决在一段连续序列（如字符串或数组）中查找满足特定条件的子序列问题。

滑动窗口算法思想:

算法的核心是维护一个由左指针 l 和右指针 r 构成的“窗口”。

1. 窗口扩张: 我们不断地将右指针 r 向右移动，扩大窗口的范围，直到这个窗口内的子串满足了题目给定的条件（即“覆盖”了字符串 t）。
2. 窗口收缩: 一旦窗口满足条件，我们就记录下当前窗口的长度，并尝试将左指针 l 向右移动，以缩小窗口。我们的目标是在保持条件满足的前提下，尽可能地缩小窗口长度，从而找到最短的子串。
3. 状态记录: 为了高效地判断窗口是否满足条件，我们需要记录两种状态：
   • 需求状态: 字符串 t 中需要被满足的字符及其数量。我们可以用一个哈希表或数组 need 来记录。
   • 窗口状态: 当前窗口内已经包含的字符及其数量。我们用另一个哈希表或数组 win 来记录。
   • 满足度: 用一个变量 vld (valid) 来记录 win 中有多少种字符已经满足了 need 的数量要求。当 vld 的值等于 need 中不同字符的总数时，窗口就满足了条件。

具体流程:

1. 初始化 need 表来统计 t 中的字符。初始化 win 表为空。l, r, vld 均置为 0。同时，用变量 st 和 len 分别记录最终答案的起始位置和最小长度（len 初始为无穷大）。
2. 右指针 r 开始向右遍历 s，将 s[r] 纳入窗口并更新 win。
3. 如果 s[r] 是 t 中需要的字符，并且 win[s[r]] 的数量刚好达到 need[s[r]] 的要求，则 vld 加一。
4. 当 vld 等于 need 中不同字符的总数时，说明窗口已达标，此时进入收缩阶段。
5. 在收缩窗口前，先判断当前窗口长度是否比已记录的 len 更小，如果是，则更新 st 和 len。
6. 然后，将左指针 l 向右移动，将 s[l] 移出窗口并更新 win。如果 s[l] 是 t 中需要的字符，且移出后 win[s[l]] 的数量不再满足 need[s[l]] 的要求，则 vld 减一。
7. 重复收缩步骤，直到窗口不再满足条件，然后继续扩张窗口。
8. 当 r 遍历完整个 s 后，算法结束。如果 len 仍然是无穷大，则无解；否则，根据 st 和 len 截取子串即为最终答案。

此算法的时间复杂度为 $O(|S| + |T|)$，空间复杂度为 $O(K)$（其中 $K$ 为字符集大小）。

C++ 解决方案

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void slv() {
    string s, t;
    cin >> s >> t;

    // 用数组代替哈希表，提高效率
    int need[128] = {0};
    int win[128] = {0};
    int cnt = 0; // t中不同字符的种类数

    for (char c : t) {
        if (need[c] == 0) {
            cnt++;
        }
        need[c]++;
    }

    int l = 0, r = 0;
    int vld = 0; // 窗口中满足条件的字符种类数

    int st = 0;         // 结果子串的起始位置
    int len = INT_MAX;  // 结果子串的长度

    while (r < s.size()) {
        char c = s[r];
        r++;

        // 如果是t中需要的字符，则更新窗口数据
        if (need[c]) {
            win[c]++;
            if (win[c] == need[c]) {
                vld++;
            }
        }

        // 当窗口满足条件时，开始收缩左边界
        while (vld == cnt) {
            // 更新最小覆盖子串的结果
            if (r - l < len) {
                st = l;
                len = r - l;
            }

            char d = s[l];
            l++;

            // 如果移出的字符是t中需要的，则更新窗口数据
            if (need[d]) {
                if (win[d] == need[d]) {
                    vld--;
                }
                win[d]--;
            }
        }
    }

    // 如果len未被更新过，说明没有找到，输出空串
    if (len == INT_MAX) {
        cout << "" << endl;
    } else {
        cout << s.substr(st, len) << endl;
    }
}

int main() {
    // 关闭同步流，加速IO
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    slv();

    return 0;
}

/*
样例输入 1:
ADOBECODEBANC
ABC

样例输出 1:
BANC

样例输入 2:
a
aa

样例输出 2:

*/