LeetCode 1297. 子串的最大出現次數（定長滑動視窗圖解）

1297. 子串的最大出現次數

題目描述

給你一個字串 s，請你回傳滿足以下條件且出現次數最大的任意子串的出現次數：

• 子串中不同字母的數目必須小於等於 maxLetters。
• 子串的長度必須大於等於 minSize 且小於等於 maxSize。

範例 1

輸入：s = "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4
輸出：2
解釋：子串 "aab" 在原字串中出現了 2 次。
它滿足所有的要求：2 個不同的字母，長度為 3（在 minSize 和 maxSize 範圍內）。

範例 2

輸入：s = "aaaa", maxLetters = 1, minSize = 3, maxSize = 3
輸出：2
解釋：子串 "aaa" 在原字串中出現了 2 次，且它們有重疊部分。

範例 3

輸入：s = "aabcabcab", maxLetters = 2, minSize = 2, maxSize = 3
輸出：3

範例 4

輸入：s = "abcde", maxLetters = 2, minSize = 3, maxSize = 3
輸出：0

注意：出現次數允許子串互相重疊（範例 2）。

本文題解思路與程式碼整理自 LeetCode 題解作者「灵茶山艾府」，題解連結。圖解與步驟說明為自行補充。

前置知識：定長滑動視窗

定長視窗每次右移一格，少一個最左邊的元素、多一個新元素，視窗內的資訊可以用「加新的、減舊的」在 O(1) 內更新。前面幾篇已經用過，例如 2841，同樣要統計視窗內的不同元素個數。

思路

這題有三個條件互相牽制（不同字母數、最短長度、最長長度），乍看很複雜，其實可以先把它簡化成只看一種長度。

第一步：只需要看長度恰好等於 minSize 的子串

兩個觀察：

1. 子串越短，包含的不同字母越少，越容易滿足 不同字母數 <= maxLetters。
2. 子串越短，在 s 裡出現的次數越多（或一樣多）。

把這兩點合起來，用一句話說明為什麼 maxSize 是多餘的：

設一個合法的子串 T，長度大於 minSize。取 T 的前 minSize 個字元，得到 P。

• P 的不同字母數 ≤ T 的不同字母數 ≤ maxLetters，所以 P 也合法。
• T 每出現一次，P 就跟著在同一個起點出現一次，所以 P 的出現次數 ≥ T 的出現次數。

也就是說，任何比 minSize 長的合法子串，都有一個長度恰好是 minSize 的合法子串不比它差。因此答案只需要在長度等於 minSize 的子串裡找。

下面用範例 1 實際比較。切換長度 3 和長度 4，看每個子串是否有效、各出現幾次：

選一個子串長度：長度 3（minSize）長度 4（maxSize）

s = "aababcaab"，maxLetters = 2，minSize = 3，maxSize = 4（亮起來的是「出現最多次的有效子串」出現的位置）

可以看到長度 3 的最大次數（2）不小於長度 4 的最大次數（1），和上面的推論一致。

第二步：用定長滑動視窗列舉所有長度為 minSize 的子串

視窗長度固定為 minSize，每滑一格需要維護兩件事：

1. 視窗內有幾種不同的字母（kinds），用來判斷是否 <= maxLetters。
2. 這個子串之前出現過幾次（strCnt），用雜湊表記錄，每次更新答案。

第三步：怎麼維護「不同字母的數目」

不需要每次重新數。用長度 26 的陣列 charCnt 記錄視窗內每個字母出現幾次：

• 字母進入視窗：先看它之前的次數，如果是 0，代表是新字母，kinds 加一；再把次數加一。
• 字母離開視窗：先把次數減一，如果減完是 0，代表視窗裡沒有這個字母了，kinds 減一。

這和 2841 用雜湊表統計不同元素是同一個想法，這裡字母只有小寫 26 個，用陣列比雜湊表更快。

第四步：統計子串出現次數

題目保證 minSize <= 26，子串很短，直接把子串字串當雜湊表的 key 就夠了（substring 一次最多複製 26 個字元）。如果 minSize 可以很大，就需要用字典樹來加速，這題不用。

圖解（可互動）

用範例 1：s = "aababcaab"，maxLetters = 2，視窗長度 minSize = 3。重點看三件事：

• 視窗 "abc"、"bca" 有 3 種不同字母，超過 maxLetters，直接跳過，不計入子串次數。
• 最後一個視窗 "aab" 是第二次出現，所以 ans 從 1 變成 2。
• 字母離開視窗時，只有在次數歸零才讓 kinds 減一。

上一步 下一步 重置

s = "aababcaab"，maxLetters = 2，窗口長度 = minSize = 3

窗口 不同字母太多，不算 入 = 新進入 出 = 更新後離開

窗口內不同字母 kinds0

目前最大次數 ans0

把過程寫成表格：

視窗	子串	kinds	是否有效	strCnt 之後	ans
[0,2]	aab	2	是	aab:1	1
[1,3]	aba	2	是	aab:1, aba:1	1
[2,4]	bab	2	是	aab:1, aba:1, bab:1	1
[3,5]	abc	3	否（超過 2）	不變	1
[4,6]	bca	3	否（超過 2）	不變	1
[5,7]	caa	2	是	…, caa:1	1
[6,8]	aab	2	是	aab:2, …	2

最後 ans = 2，與範例 1 一致。

範例 2 s = "aaaa"、minSize = 3：視窗是 [0,2] 和 [1,3]，都是 "aaa"，只有 1 種字母，strCnt["aaa"] = 2。題目允許重疊，所以答案是 2。

解法（灵茶山艾府）

class Solution {
    public int maxFreq(String S, int maxLetters, int minSize, int maxSize) {
        char[] s = S.toCharArray();
        Map<String, Integer> strCnt = new HashMap<>();
        int[] charCnt = new int[26];
        int kinds = 0;
        int ans = 0;

        for (int i = 0; i < s.length; i++) {
            // 1. 進入視窗
            int in = s[i] - 'a';
            if (charCnt[in] == 0) {
                kinds++;
            }
            charCnt[in]++;

            int left = i - minSize + 1;
            if (left < 0) { // 視窗大小不足 minSize
                continue;
            }

            // 2. 更新統計量
            if (kinds <= maxLetters) {
                String subStr = S.substring(left, left + minSize);
                int cnt = strCnt.merge(subStr, 1, Integer::sum); // cnt = ++strCnt[subStr];
                ans = Math.max(ans, cnt);
            }

            // 3. 離開視窗，為下一個迴圈做準備
            int out = s[left] - 'a';
            charCnt[out]--;
            if (charCnt[out] == 0) {
                kinds--;
            }
        }

        return ans;
    }
}

幾個細節：

• maxSize 參數完全沒用到，這就是第一步推論的結果。
• 進入視窗時先判斷 charCnt[in] == 0 再加一；離開視窗時先減一再判斷 == 0，順序反了 kinds 就會算錯。
• strCnt.merge(subStr, 1, Integer::sum) 等價於 ++strCnt[subStr]，並直接回傳更新後的次數。
• 只有 kinds <= maxLetters 的視窗才把子串放進 strCnt，不合格的子串完全不計。

複雜度分析

• 時間複雜度：O((n − minSize) · minSize)，其中 n 是 s 的長度。有 n − minSize + 1 個視窗，每個視窗取子串並計算雜湊要 O(minSize)。
• 空間複雜度：O((n − minSize) · minSize)。雜湊表最多存 n − minSize + 1 個子串，每個長 minSize。