<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                合規國際互聯網加速 OSASE為企業客戶提供高速穩定SD-WAN國際加速解決方案。 廣告
                # 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">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxFreq</span><span class="hljs-params">(self, s: str, maxLetters: int, minSize: int, maxSize: int)</span> -> int:</span> n = len(s) letters = set() cnts = dict() res = <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n - minSize + <span class="hljs-params">1</span>): length = minSize <span class="hljs-keyword">while</span> i + length <= n <span class="hljs-keyword">and</span> length <= maxSize: t = s[i:i + length] <span class="hljs-keyword">for</span> c <span class="hljs-keyword">in</span> t: <span class="hljs-keyword">if</span> len(letters) > maxLetters: <span class="hljs-keyword">break</span> letters.add(c) <span class="hljs-keyword">if</span> len(letters) <= maxLetters: cnts[t] = cnts.get(t, <span class="hljs-params">0</span>) + <span class="hljs-params">1</span> res = max(res, cnts[t]) letters.clear() length += <span class="hljs-params">1</span> <span class="hljs-keyword">return</span> res ``` ``` 上述代碼會超時。我們來利用剪枝來優化。 ## 剪枝 ### 思路 還是暴力法的思路,不過我們在此基礎上進行一些優化。首先我們需要仔細閱讀題目,如果你足夠細心或者足夠有經驗,可能會發現其實題目中 maxSize 沒有任何用處,屬于干擾信息。 也就是說我們沒有必要統計`長度大于等于 minSize 且小于等于 maxSize 的所有子串`,而是統計長度為 minSize 的所有字串即可。原因是,如果一個大于 minSize 長度的字串若是滿足條件,那么該子串其中必定有至少一個長度為 minSize 的字串滿足條件。因此一個大于 minSize 長度的字串出現了 n 次,那么該子串其中必定有一個長度為 minSize 的子串出現了 n 次。 ### 代碼 代碼支持 Python3,Java: Python Code: ``` <pre class="calibre18">``` <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxFreq</span><span class="hljs-params">(self, s: str, maxLetters: int, minSize: int, maxSize: int)</span> -> int:</span> counter, res = {}, <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-params">0</span>, len(s) - minSize + <span class="hljs-params">1</span>): sub = s[i : i + minSize] <span class="hljs-keyword">if</span> len(set(sub)) <= maxLetters: counter[sub] = counter.get(sub, <span class="hljs-params">0</span>) + <span class="hljs-params">1</span> res = max(res, counter[sub]) <span class="hljs-keyword">return</span> res; <span class="hljs-title"># @lc code=end</span> ``` ``` Java Code: ``` <pre class="calibre18">``` <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">maxFreq</span><span class="hljs-params">(String s, <span class="hljs-keyword">int</span> maxLetters, <span class="hljs-keyword">int</span> minSize, <span class="hljs-keyword">int</span> maxSize)</span> </span>{ Map<String, Integer> counter = <span class="hljs-keyword">new</span> HashMap<>(); <span class="hljs-keyword">int</span> res = <span class="hljs-params">0</span>; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-params">0</span>; i < s.length() - minSize + <span class="hljs-params">1</span>; i++) { String substr = s.substring(i, i + minSize); <span class="hljs-keyword">if</span> (checkNum(substr, maxLetters)) { <span class="hljs-keyword">int</span> newVal = counter.getOrDefault(substr, <span class="hljs-params">0</span>) + <span class="hljs-params">1</span>; counter.put(substr, newVal); res = Math.max(res, newVal); } } <span class="hljs-keyword">return</span> res; } <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">checkNum</span><span class="hljs-params">(String substr, <span class="hljs-keyword">int</span> maxLetters)</span> </span>{ Set<Character> set = <span class="hljs-keyword">new</span> HashSet<>(); <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-params">0</span>; i < substr.length(); i++) set.add(substr.charAt(i)); <span class="hljs-keyword">return</span> 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)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看