76. 最小覆盖子串。优化官方题解！

leetcode原题如下：

????????

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

注意：

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

????????

解题思路---滑动窗口

如何判断当前的窗口包含所有 t 所需的字符呢？我们可以用一个哈希表表示 t 中所有的字符以及它们的个数，用一个哈希表动态维护窗口中所有的字符以及它们的个数，如果这个动态表中包含 t 的哈希表中的所有字符，并且对应的个数都不小于 t 的哈希表中各个字符的个数，那么当前的窗口是「可行」的。

官方题解：

    Map<Character, Integer> ori = new HashMap<Character, Integer>();
    Map<Character, Integer> cnt = new HashMap<Character, Integer>();

    public String minWindow(String s, String t) {
            Map<Character, Integer> ori = new HashMap<>();
        Map<Character, Integer> cnt = new HashMap<>();

        // 预处理，初始化 ori 表
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            ori.put(c, ori.getOrDefault(c, 0) + 1);
        }

        int l = 0, r = 0;
        int len = Integer.MAX_VALUE, ansL = -1, ansR = -1;
        int sLen = s.length();
        int required = ori.size();  // 需要匹配的字符种类数量
        int formed = 0;  // 已经匹配的字符种类数量

        while (r < sLen) {
            char c = s.charAt(r);
            cnt.put(c, cnt.getOrDefault(c, 0) + 1);

            if (ori.containsKey(c) && cnt.get(c).equals(ori.get(c))) {
                formed++;
            }

            while (formed == required && l <= r) {
                if (r - l + 1 < len) {
                    len = r - l + 1;
                    ansL = l;
                    ansR = l + len;
                }

                char leftChar = s.charAt(l);
                cnt.put(leftChar, cnt.get(leftChar) - 1);

                if (ori.containsKey(leftChar) && cnt.get(leftChar) < ori.get(leftChar)) {
                    formed--;
                }

                l++;
            }

            r++;
        }

        return ansL == -1 ? "" : s.substring(ansL, ansR);
    }

注意：这里 t 中可能出现重复的字符，所以我们要记录字符的个数。

考虑如何优化？ 如果 s=XX?XABCXXXX,t=ABC，那么显然 [XX?XABC]是第一个得到的「可行」区间，得到这个可行区间后，我们按照「收缩」窗口的原则更新左边界，得到最小区间。我们其实做了一些无用的操作，就是更新右边界的时候「延伸」进了很多无用的 X，更新左边界的时候「收缩」扔掉了这些无用的 X，做了这么多无用的操作，只是为了得到短短的 ABC。没错，其实在 s 中，有的字符我们是不关心的，我们只关心 t中出现的字符，我们可不可以先预处理 s，扔掉那些 t?中没有出现的字符，然后再做滑动窗口呢？也许你会说，这样可能出现 XXABXXC的情况，在统计长度的时候可以扔掉前两个 X，但是不扔掉中间的 X，怎样解决这个问题呢？优化后的时空复杂度又是多少？代码给出优化的版本.

public class MinimumWindowSubstring {
    public String minWindow(String s, String t) {
        // 用于记录 t 中各字符需要匹配的次数
        Map<Character, Integer> ori = new HashMap<>();

        // 用于记录当前窗口中各字符已匹配的次数
        Map<Character, Integer> cnt = new HashMap<>();

        // 预处理，初始化 ori 表
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            ori.put(c, ori.getOrDefault(c, 0) + 1);
        }

        int l = 0, r = 0; // 窗口的左右边界
        int len = Integer.MAX_VALUE; // 记录当前最小窗口的长度
        int ansL = -1, ansR = -1; // 记录当前最小窗口的左右边界
        int sLen = s.length(); // 字符串 s 的长度

        int required = ori.size(); // 需要匹配的字符种类数量
        int formed = 0; // 已经匹配的字符种类数量

        // 右指针滑动
        while (r < sLen) {
            char c = s.charAt(r);
            cnt.put(c, cnt.getOrDefault(c, 0) + 1);

            // 如果当前字符在 ori 表中，并且已匹配次数等于 ori 表中的次数，增加已匹配字符种类数量
            if (ori.containsKey(c) && cnt.get(c).equals(ori.get(c))) {
                formed++;
            }

            // 左指针滑动，窗口收缩
            while (formed == required && l <= r) {
                // 更新最小窗口的长度和边界
                if (r - l + 1 < len) {
                    len = r - l + 1;
                    ansL = l;
                    ansR = l + len;
                }

                // 移动左指针，减少已匹配字符的次数
                char leftChar = s.charAt(l);
                cnt.put(leftChar, cnt.get(leftChar) - 1);

                // 如果左边界字符在 ori 表中，并且减少后的次数小于 ori 表中的次数，减少已匹配字符种类数量
                if (ori.containsKey(leftChar) && cnt.get(leftChar) < ori.get(leftChar)) {
                    formed--;
                }

                l++;
            }

            // 右指针继续滑动
            r++;
        }

        // 返回最小窗口对应的子串
        return ansL == -1 ? "" : s.substring(ansL, ansR);
    }
}

这段代码中的核心思想是使用滑动窗口来找到包含字符串 t 中所有字符的最小窗口。下面是代码中各部分的解释：

1. ori 和 cnt 的初始化：

   • ori 表用于记录字符串 t 中各字符需要匹配的次数。
   • cnt 表用于记录当前窗口中各字符已匹配的次数。

2. 预处理，初始化 ori 表：

   • 遍历字符串 t，将其中各字符及其需要匹配的次数记录在 ori 表中。

3. 窗口的左右边界 l 和 r：

   • 使用两个指针 l 和 r 来确定窗口。

4. required 和 formed：

   • required 记录需要匹配的字符种类数量，即 ori 表的大小。
   • formed 记录已经匹配的字符种类数量，初始为 0。

5. 右指针滑动（while (r < sLen)）：

   • 不断移动右指针 r，直到窗口包含了字符串 s 中的所有字符。

6. 左指针滑动，窗口收缩（while (formed == required && l <= r)）：

   • 移动左指针 l，尝试缩小窗口的大小。
   • 更新最小窗口的长度和边界。

7. 左右指针继续滑动，直至右指针到达字符串末尾：