在给定两个字符串 s 和 t 的情境下，我们的目标是从 s 中寻找到一个最短的子串，该子串必须包含 t 中的所有字符。值得注意的是，如果 t 中存在重复字符，那么在 s 的子串中，对应字符的数量也必须至少达到 t 中所需的数量。若 s 中不存在满足条件的子串，则应返回空字符串 ""。

重要约束：

• s 和 t 均由英文字母组成。
• s 的长度 m，t 的长度 n，满足 1 <= m, n <= 10^5。
• 如果存在多个满足条件的最小子串，题目保证它们是唯一的。

示例：

<strong>示例 1：</strong>
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：子串 "BANC" 是 s 中涵盖 t ('A', 'B', 'C') 所有字符的最短子串。

<strong>示例 2：</strong>
输入：s = "a", t = "a"
输出："a"
解释：s 本身就是包含 t 的最小子串。

<strong>示例 3：</strong>
输入：s = "a", t = "aa"
输出：""
解释：t 需要两个 'a'，但 s 中只有一个，因此无法找到满足条件的子串。

算法核心思想：滑动窗口

解决此类字符串匹配并寻找最小范围的问题，滑动窗口（Sliding Window）算法是一种高效且常用的策略。其核心思想是维护一个动态调整大小的窗口，通过两个指针（通常称为左指针 left 和右指针 right）来控制窗口的边界，并在窗口滑动过程中不断检查是否满足特定条件。

具体步骤：

1. 预处理目标字符计数： 首先，遍历字符串 t，使用一个哈希表或数组来记录其中每个字符及其所需的出现频率。这将作为我们判断窗口是否满足条件的依据。
2. 初始化窗口状态： 设置两个指针 left 和 right，均从字符串 s 的起始位置（索引 0）开始。同时初始化一个变量来记录当前已匹配 t 中多少个独特字符（即，窗口内这些独特字符的计数已达到或超过 t 中所需）。
3. 扩展窗口： right 指针逐个向右移动，将 s 中的字符纳入当前窗口。每纳入一个字符，更新窗口内该字符的计数。如果该字符是 t 所需的字符，并且其在窗口内的计数首次达到 t 中所需的数量，则增加已匹配独特字符的计数。
4. 收缩窗口： 当窗口内已匹配独特字符的计数达到 t 中所有独特字符的总数时，说明当前窗口已经包含了 t 的所有字符。此时，我们尝试移动 left 指针向右收缩窗口，以寻找更短的满足条件的子串：
   • 记录当前窗口的长度以及起始位置，如果它比之前找到的最小长度更小，则更新最优解。
   • 将 left 指针指向的字符从窗口中移除，并减少其在窗口内的计数。
   • 如果移除的字符是 t 所需的字符，并且其在窗口内的计数首次低于 t 中所需的数量，则减少已匹配独特字符的计数。
   • 继续移动 left 指针，直到窗口不再满足包含 t 所有字符的条件。
5. 循环迭代： 重复步骤 3 和 4，直到 right 指针遍历完整个 s 字符串。

复杂度分析：

• 时间复杂度： O(m + n)，其中 m 是 s 的长度，n 是 t 的长度。这是因为滑动窗口的 left 和 right 指针最多各自遍历 s 字符串一次。字符计数的哈希表操作平均为 O(1)。
• 空间复杂度： O(∣Σ∣)，其中 ∣Σ∣ 是字符集的大小（例如，ASCII 字符集大小为 128 或 256）。这部分空间用于存储字符频率映射。

C++ 代码实现

#include <string>
#include <vector>
#include <algorithm> // For std::min

// 定义一个函数来查找 s 中涵盖 t 所有字符的最小子串
std::string findMinCoveringSubstring(const std::string& sourceStr, const std::string& targetStr) {
    // 如果目标字符串 t 为空，直接返回空字符串
    if (targetStr.empty()) {
        return "";
    }

    // 使用数组存储目标字符串 t 中每个字符所需的频率
    // 假设字符集为 ASCII，大小为 128
    std::vector<int> targetCharCounts(128, 0);
    for (char c : targetStr) {
        targetCharCounts[c]++;
    }

    // 统计目标字符串 t 中独特字符的数量
    int requiredUniqueChars = 0;
    for (int count : targetCharCounts) {
        if (count > 0) {
            requiredUniqueChars++;
        }
    }

    // 使用数组存储当前滑动窗口中每个字符的频率
    std::vector<int> windowCharCounts(128, 0);
    // 记录当前窗口中，有多少个独特的目标字符已满足其所需频率
    int currentMatchedUniqueChars = 0;

    // 滑动窗口的左指针
    int leftPtr = 0;
    // 记录找到的最小子串的长度，初始化为一个不可能达到的最大值
    int minSubstringLength = sourceStr.length() + 1;
    // 记录最小子串的起始索引
    int minSubstringStartIdx = 0;

    // 遍历源字符串 s，rightPtr 作为滑动窗口的右指针
    for (int rightPtr = 0; rightPtr < sourceStr.length(); ++rightPtr) {
        char currentChar = sourceStr[rightPtr];
        windowCharCounts[currentChar]++; // 将当前字符加入窗口

        // 如果当前字符是目标字符，并且其在窗口内的计数首次达到目标所需计数
        if (targetCharCounts[currentChar] > 0 && windowCharCounts[currentChar] == targetCharCounts[currentChar]) {
            currentMatchedUniqueChars++; // 增加已匹配独特字符的数量
        }

        // 当窗口内的字符满足了 t 中所有独特字符的需求时
        while (currentMatchedUniqueChars == requiredUniqueChars) {
            // 更新最小子串的长度和起始位置
            if (rightPtr - leftPtr + 1 < minSubstringLength) {
                minSubstringLength = rightPtr - leftPtr + 1;
                minSubstringStartIdx = leftPtr;
            }

            // 尝试收缩窗口，移动左指针
            char leftChar = sourceStr[leftPtr];
            windowCharCounts[leftChar]--; // 将左指针指向的字符移出窗口

            // 如果移出的字符是目标字符，并且其在窗口内的计数首次低于目标所需计数
            if (targetCharCounts[leftChar] > 0 && windowCharCounts[leftChar] < targetCharCounts[leftChar]) {
                currentMatchedUniqueChars--; // 减少已匹配独特字符的数量
            }

            leftPtr++; // 移动左指针
        }
    }

    // 如果 minSubstringLength 仍然是初始值，说明没有找到符合条件的子串
    if (minSubstringLength > sourceStr.length()) {
        return "";
    }

    // 返回找到的最小子串
    return sourceStr.substr(minSubstringStartIdx, minSubstringLength);
}

算法启示与实际应用

该算法的关键在于滑动窗口机制的巧妙运用。通过双指针实现窗口的动态伸缩，避免了对子串的重复扫描，从而将时间复杂度优化到线性级别。同时，借助于字符频率映射（例如哈希表或定长数组），我们可以 O(1) 地检查窗口内字符是否满足目标条件，极大提升了判断效率。

在实际应用中，寻找最小覆盖子串的算法在多个场景下都展现出其价值。例如，在搜索引擎的文档摘要生成功能中，当用户输入一组关键词时，系统需要从浩瀚的文档内容中提取出最短且能同时涵盖所有关键词的段落作为搜索结果的摘要。这不仅能帮助用户快速把握文档核心内容，也提升了搜索体验。此外，在日志分析、基因序列匹配等领域，也有类似需求，即在长序列中查找包含特定模式的最短子序列。