最小覆蓋子串

難度 - 困難
原題鏈接 - 最小覆蓋字串

給你一個字符串 s 、一個字符串 t 。返回 s 中涵蓋 t 所有字符的最小子串。如果 s 中不存在涵蓋 t 所有字符的子串，則返回空字符串 “” 。
注意：
對于 t 中重復(fù)字符，我們尋找的子字符串中該字符數(shù)量必須不少于 t 中該字符數(shù)量。
如果 s 中存在這樣的子串，我們保證它是唯一的答案。

示例 1：
輸入：s = “ADOBECODEBANC”, t = “ABC”
輸出：“BANC”
解釋：最小覆蓋子串 “BANC” 包含來自字符串 t 的 ‘A’、‘B’ 和 ‘C’。

示例 2：
輸入：s = “a”, t = “a”
輸出：“a”
解釋：整個字符串 s 是最小覆蓋子串。

示例 3:
輸入: s = “a”, t = “aa”
輸出: “”
解釋: t 中兩個字符 ‘a(chǎn)’ 均應(yīng)包含在 s 的子串中，
因此沒有符合條件的子字符串，返回空字符串。

提示：
m == s.length
n == t.length
1 <= m, n <= 1e5
s 和 t 由英文字母組成

滑動窗口

這個算法技巧的思路非常簡單，就是維護(hù)一個窗口，不斷滑動，然后更新答案么.
該算法的大致邏輯如下：

int left = 0, right = 0;

while (left < right && right < s.size()) {
    // 增大窗口
    window.add(s[right]);
    right++;
    
    while (window needs shrink) {
        // 縮小窗口
        window.remove(s[left]);
        left++;
    }
}

這個算法技巧的時間復(fù)雜度是 O(N)，比字符串暴力算法要高效得多。

本題的解題思路：
1、我們在字符串 S 中使用雙指針中的左右指針技巧，初始化 left = right = 0，把索引左閉右開區(qū)間 [left, right) 稱為一個「窗口」。
理論上你可以設(shè)計兩端都開或者兩端都閉的區(qū)間，但設(shè)計為左閉右開區(qū)間是最方便處理的。因?yàn)檫@樣初始化 left = right = 0 時區(qū)間 [0, 0) 中沒有元素，但只要讓 right 向右移動（擴(kuò)大）一位，區(qū)間 [0, 1) 就包含一個元素 0 了。如果你設(shè)置為兩端都開的區(qū)間，那么讓 right 向右移動一位后開區(qū)間 (0, 1) 仍然沒有元素；如果你設(shè)置為兩端都閉的區(qū)間，那么初始區(qū)間 [0, 0] 就包含了一個元素。這兩種情況都會給邊界處理帶來不必要的麻煩。

2、我們先不斷地增加 right 指針擴(kuò)大窗口 [left, right)，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。

3、此時，我們停止增加 right，轉(zhuǎn)而不斷增加 left 指針縮小窗口 [left, right)，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同時，每次增加 left，我們都要更新一輪結(jié)果。

4、重復(fù)第 2 和第 3 步，直到 right 到達(dá)字符串 S 的盡頭。

這個思路其實(shí)也不難，第 2 步相當(dāng)于在尋找一個「可行解」，然后第 3 步在優(yōu)化這個「可行解」，最終找到最優(yōu)解，也就是最短的覆蓋子串。左右指針輪流前進(jìn)，窗口大小增增減減，窗口不斷向右滑動，這就是「滑動窗口」這個名字的來歷。

下面畫圖理解一下，needs 和 window 相當(dāng)于計數(shù)器，分別記錄 T 中字符出現(xiàn)次數(shù)和「窗口」中的相應(yīng)字符的出現(xiàn)次數(shù)。

代碼

public String minWindow1(String s, String t) {
        // 用于記錄需要的字符和窗口中的字符及其出現(xiàn)的次數(shù)
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();
        // 統(tǒng)計 t 中各字符出現(xiàn)次數(shù)
        for (char c : t.toCharArray())
            need.put(c, need.getOrDefault(c, 0) + 1);

        int left = 0, right = 0;
        int valid = 0; // 窗口中滿足需要的字符個數(shù)
        // 記錄最小覆蓋子串的起始索引及長度
        int start = 0, len = Integer.MAX_VALUE;
        while (right < s.length()) {
            // c 是將移入窗口的字符
            char c = s.charAt(right);
            // 擴(kuò)大窗口
            right++;
            // 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c).equals(need.get(c)))
                    valid++; // 只有當(dāng) window[c] 和 need[c] 對應(yīng)的出現(xiàn)次數(shù)一致時，才能滿足條件，valid 才能 +1
            }

            // 判斷左側(cè)窗口是否要收縮
            while (valid == need.size()) {
                // 更新最小覆蓋子串
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }
                // d 是將移出窗口的字符
                char d = s.charAt(left);
                // 縮小窗口
                left++;
                // 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新
                if (need.containsKey(d)) {
                    if (window.get(d).equals(need.get(d)))
                        valid--; // 只有當(dāng) window[d] 內(nèi)的出現(xiàn)次數(shù)和 need[d] 相等時，才能 -1
                    window.put(d, window.get(d) - 1);
                }
            }
        }

        // 返回最小覆蓋子串
        return len == Integer.MAX_VALUE ?
                "" : s.substring(start, start + len);
    }

上期經(jīng)典

leetcode59. 螺旋矩陣 II文章來源地址http://www.zghlxwxcb.cn/news/detail-673989.html

到了這里，關(guān)于leetcode76. 最小覆蓋子串(滑動窗口-java)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！