項目 widget-area-1 尚未註冊或是沒有一個 view.php 檔案.
項目 widget-area-1 尚未註冊或是沒有一個 view.php 檔案.
項目 search-input 尚未註冊或是沒有一個 view.php 檔案.

【Leetcode】python – [424] Longest Repeating Character Replacement 個人解法筆記 #重要題型

題目出處

424. Longest Repeating Character Replacement

難度

medium

個人範例程式碼

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:

        ans = 0
        window_counter = defaultdict(int)
        max_counter = 0
        start = 0

        for end in range(len(s)):
            # print(start, end, s[start:end+1])
            new_word = s[end]
            window_counter[new_word] += 1
            max_counter = max(max_counter, window_counter[new_word])

            # end - start + 1 = window length (delete max duplicate <= k)
            if (end - start + 1) - max_counter <= k:
                ans = max(ans, end - start + 1)     
            else: # wrong case, move window (first delete then move)
                delete_word = s[start] 
                window_counter[delete_word] -= 1
                start += 1

        return ans

算法說明

讓我們先來理解題目,這題目主要是在詢問我們在「允許替換最多 k 個文字的情況下」,
我們能夠組出的最長文字。

我們使用「sliding window」的概念,配合 counter,計算最多重複的字元。

我們可以藉由不斷移動 end,當發現 window 不滿足條件時,
我們「不改變 window 的大小 (已經是最大)」,去不斷的 move start 直到 window 有機會變得更大。

window 大小只會變大,「當發現不符合規則時,我們只會繼續移動 window,不會縮小 window

input handling

一同在 for 內處理

Boundary conditions

用 for 來控制範圍

Reference

⭐ Leetcode 解題紀錄 ⭐題型資料結構Python SolutionC++ SolutionNote
⭐BFS 相關題型 ⭐
104Maximum Depth of Binary TreeBFS (分層)Python
94Binary Tree Inorder TraversalBFS (分層)TreePython 內含 處理 Tree 樹問題的重點
102Binary Tree Level Order TraversalBFS (分層)TreePython
103Binary Tree Zigzag Level Order TraversalBFS (分層)TreePython
107Binary Tree Level Order Traversal IIBFS (分層)TreePython
133Clone GraphBFS (分層)GraphPython Graph 的基本操作 #重要題型
127Word LadderBFS (分層), DFSGraphPython
[Lint] 127Topological SortingBFS (拓撲)Python
內有 indegree, outdegree 介紹 #重要題型
207Course ScheduleBFS (拓樸)GraphPython
210Course Schedule IIBFS (拓樸)GraphPython
[Lint] 892Alien DictionaryBFS (拓樸)