1297. 子串的最大出現次數 · ttttt

# 1297. 子串的最大出現次數 # 題目地址（1297. 子串的最大出現次數） <https://leetcode-cn.com/problems/maximum-number-of-occurrences-of-a-substring/> ## 題目描述 ``` <pre class="calibre18">``` 給你一個字符串 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 提示： 1 <= s.length <= 10^5 1 <= maxLetters <= 26 1 <= minSize <= maxSize <= min(26, s.length) s 只包含小寫英文字母。 ``` ``` ## 前置知識 - 字符串 - 滑動窗口 ## 暴力法題目給的數據量不是很大，為 1 <= maxLetters <= 26，我們試一下暴力法。 ## 公司 - 字節 ### 思路暴力法如下： - 先找出所有滿足長度大于等于 minSize 且小于等于 maxSize 的所有子串。（平方的復雜度） - 對于 maxLetter 滿足題意的子串，我們統計其出現次數。時間復雜度為 O(k),其中 k 為子串長度 - 返回最大的出現次數 ### 代碼 Pythpn Code: ``` <pre class="calibre18">``` class Solution: def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int: n = len(s) letters = set() cnts = dict() res = 0 for i in range(n - minSize + 1): length = minSize while i + length <= n and length <= maxSize: t = s[i:i + length] for c in t: if len(letters) > maxLetters: break letters.add(c) if len(letters) <= maxLetters: cnts[t] = cnts.get(t, 0) + 1 res = max(res, cnts[t]) letters.clear() length += 1 return res ``` ``` 上述代碼會超時。我們來利用剪枝來優化。 ## 剪枝 ### 思路還是暴力法的思路，不過我們在此基礎上進行一些優化。首先我們需要仔細閱讀題目，如果你足夠細心或者足夠有經驗，可能會發現其實題目中 maxSize 沒有任何用處，屬于干擾信息。也就是說我們沒有必要統計`長度大于等于 minSize 且小于等于 maxSize 的所有子串`，而是統計長度為 minSize 的所有字串即可。原因是，如果一個大于 minSize 長度的字串若是滿足條件，那么該子串其中必定有至少一個長度為 minSize 的字串滿足條件。因此一個大于 minSize 長度的字串出現了 n 次，那么該子串其中必定有一個長度為 minSize 的子串出現了 n 次。 ### 代碼代碼支持 Python3，Java： Python Code： ``` <pre class="calibre18">``` def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int: counter, res = {}, 0 for i in range(0, len(s) - minSize + 1): sub = s[i : i + minSize] if len(set(sub)) <= maxLetters: counter[sub] = counter.get(sub, 0) + 1 res = max(res, counter[sub]) return res; # @lc code=end ``` ``` Java Code： ``` <pre class="calibre18">``` public int maxFreq(String s, int maxLetters, int minSize, int maxSize) { Map<String, Integer> counter = new HashMap<>(); int res = 0; for (int i = 0; i < s.length() - minSize + 1; i++) { String substr = s.substring(i, i + minSize); if (checkNum(substr, maxLetters)) { int newVal = counter.getOrDefault(substr, 0) + 1; counter.put(substr, newVal); res = Math.max(res, newVal); } } return res; } public boolean checkNum(String substr, int maxLetters) { Set<Character> set = new HashSet<>(); for (int i = 0; i < substr.length(); i++) set.add(substr.charAt(i)); return set.size() <= maxLetters; } ``` ``` **復雜度分析** 其中 N 為 s 長度 - 時間復雜度：O(N?minSize)O(N \* minSize)O(N?minSize) - 空間復雜度：O(N?minSize)O(N \* minSize)O(N?minSize) ## 關鍵點解析 - 滑動窗口 - 識別題目干擾信息 - 看題目限制條件，對于本題有用的信息是`1 <= maxLetters <= 26` ## 擴展我們也可以使用滑動窗口來解決，感興趣的可以試試看。大家對此有何看法，歡迎給我留言，我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。目前已經 37K star 啦。大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)