最小覆盖子串

## 1 题目

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

**注意：**

* 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
* 如果 s 中存在这样的子串，我们保证它是唯一的答案。

**示例 1：**

```txt
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
```

**示例 2：**

```txt
输入：s = "a", t = "a"
输出："a"
```

**示例 3:**

```txt
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，因此没有符合条件的子字符串，返回空字符串。
```

**提示：**

* 1 <= s.length, t.length <= 105
* s 和 t 由英文字母组成

**进阶：** 你能设计一个在 o(n) 时间内解决此问题的算法吗？

## 2 问题分析

1. 该题目可以采用**滑动窗口**来解决，基本思想为：

1. **用 $i$，$j$ 表示滑动窗口的左边界和右边界**，**通过改变 $i$、$j$ 来扩展和收缩滑动窗口**，**可以想象成一个窗口在字符串上游走**，**当这个窗口包含的元素满足条件**，即**包含字符串 $T$ 的所有元素**，**记录下这个滑动窗口的长度 $j - i + 1$**，**这些长度中的最小值就是要求的结果**。
2. 具体的步骤如下：

1. **步骤一：**
      1. **不断增加 $j$ 使滑动窗口增大**，**直到窗口包含了 $T$ 的所有元素**。
   2. **步骤二：**
      1. **不断增加 $i$ 使滑动窗口缩小**，因为是要求最小子串，所以**将不必要的元素排除在外**，**使长度减小**，**直到碰到一个必须包含的元素**，这个时候不能再扔了，再扔就不满足条件了，**记录此时滑动窗口的长度**，并**保存最小值**。
   3. **步骤三：**
      1. **让 $i$ 再增加一个位置**，这个时候**滑动窗口肯定不满足条件了**，那么**继续从步骤一开始执行**，**寻找新的满足条件的滑动窗口**，**如此反复**，**直到 $j$ 超出了字符串 $S$ 范围**。
3. 上面的步骤中会面临一个问题，那就是**如何判断滑动窗口包含了 $T$ 的所有元素**，这个问题可以通过如下的方式来解决：

1. 我们**用一个字典 `need` 来表示当前滑动窗口所需的各元素数量**，**一开始滑动窗口为空**，**用 $T$ 中各元素来初始化这个 `need`**。
   2. **当滑动窗口扩展或者收缩的时候**，去**维护这个 `need` 字典**，例如：
      1. **当滑动窗口包含某个元素**，我们就**让 `need` 中这个元素的数量减 1**，代表**所需元素减少了 1 个**。
      2. **当滑动窗口移除某个元素**，就**让 `need` 中这个元素数量加 1**。
   3. 需要注意的是，**`need` 始终记录着当前滑动窗口下**，我们**还需要的元素数量**，我们**在改变 $i$、$j$ 时**，**需同步维护 `need`**。
   4. 同时，**只要某个元素包含在滑动窗口中**，我们**就会在 `need` 中存储这个元素的数量**，**如果某个元素存储的是负数**，**就代表这个元素是多余的**，比如当 `need` 等于 `{'A': -2, 'C': 1}` 时，表示当前滑动窗口中，我们有 2 个 `A` 是多余的，同时还需要 1 个 `C`，这么做的目的就是为了步骤二中排除不必要的元素，数量为负的就是不必要的元素，而数量为 0 表示刚刚好。
   5. 因此，**当 `need` 中所有元素的数量都小于等于 0 时**，**表示当前滑动窗口不再需要任何元素**。
4. 但是上面的方法存在一个问题，**如果每次判断滑动窗口是否包含了 $T$ 的所有元素**，**都去遍历 `need` 看是否所有元素数量都小于等于 0**，这个**会耗费 $O(k)$ 的时间复杂度**，其中 $k$ 代表字典长度，最坏情况下，$k$ 可能等于 $len(S)$。
5. 其实这个是可以避免的，我们**可以维护一个额外的变量 `needCnt` 来记录所需元素的总数量**，**当我们碰到一个所需元素 `c`**，**不仅 `need[c]` 的数量减少 1**，**同时 `needCnt` 也要减少 1**，这样我们**通过 `needCnt` 就可以知道是否满足条件**，而**无需遍历字典了**。
6. 具体示例如下，假设 `S = "DOABECODEBANC"`，`T = "ABC"`：

![](/media/202206/2022-06-04_120626_183038.png)

## 3 参考代码

```java
/**
 * 76. 最小覆盖子串
 * @param s 第一个字符串
 * @param t 第二个字符串
 * @return  s 中涵盖 t 所有字符的最小子串
 */
public String minWindow(String s, String t) {
    //  起始位置以及两个字符串的长度
    int i = 0, j = 0, m = s.length(), n = t.length();
    //  当前滑动窗口中需要的各元素的数量
    Map<Character, Integer> need = new HashMap<>();
    //  所需元素的总数量，当给参数为 0 时说明滑动窗口中的元素包含了 t 中所有的元素，这样可以避免遍历 need 中的元素的值是否都小于等于 0
    int needCnt = n;
    //  最后的结果
    String res = "";

//  对 need 中的元素进行初始化
    for (int k = 0; k < n; k++) {
        char key = t.charAt(k);
        if (!need.containsKey(key)) {need.put(key, 1);}
        else {
            int value = need.get(key);
            need.put(key, value + 1);
        }
    }

while (i < m) {
        //  移动 j，使得滑动窗口中包含 t 中所有的元素
        while (needCnt > 0 && j < m) {
            char key = s.charAt(j);
            if (need.containsKey(key)) {
                need.put(key, need.get(key) - 1);
                if (need.get(key) >= 0) {needCnt--;}
            }
            j++;
        }

//  移动 i，使得滑动窗口的起始位置为 t 中包含的元素，然后将 i 移动到下一个位置，进行下一次遍历
        while (i < m) {
            char key = s.charAt(i);
            if (need.containsKey(key)) {
                //  更新最后的结果，包含两种情况：
                //      1. res 为空，且 needCnt 为 0.
                //      2. res 不为空，且 此时滑动窗口的长度小于 res 的长度，且 needCnt 为 0
                if (((res == "") || (res != "" && j - i < res.length())) && needCnt == 0) {res = s.substring(i, j);}
                need.put(key, need.get(key) + 1);
                //  只有当当前 key 对应的值大于 0 时才说明滑动窗口中不包含该元素，此时才将 needCnt 加 1
                if (need.get(key) > 0) {
                    needCnt++;
                }
                i++;
                break;
            }
            i++;
        }
    }

//  返回最后结果
    return res;
}
```

## 参考文献

1. [76. 最小覆盖子串](https://leetcode-cn.com/problems/minimum-window-substring)。
2. [简简单单，非常容易理解的滑动窗口思想](https://leetcode-cn.com/problems/minimum-window-substring/solution/tong-su-qie-xiang-xi-de-miao-shu-hua-dong-chuang-k)。