題目出處
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 Solution | C++ Solution | Note | |
---|---|---|---|---|---|---|
⭐BFS 相關題型 ⭐ | ||||||
104 | Maximum Depth of Binary Tree | BFS (分層) | Python | |||
94 | Binary Tree Inorder Traversal | BFS (分層) | Tree | Python | 內含 處理 Tree 樹問題的重點 | |
102 | Binary Tree Level Order Traversal | BFS (分層) | Tree | Python | ||
103 | Binary Tree Zigzag Level Order Traversal | BFS (分層) | Tree | Python | ||
107 | Binary Tree Level Order Traversal II | BFS (分層) | Tree | Python | ||
133 | Clone Graph | BFS (分層) | Graph | Python | Graph 的基本操作 #重要題型 | |
127 | Word Ladder | BFS (分層), DFS | Graph | Python | ||
[Lint] 127 | Topological Sorting | BFS (拓撲) | Python | 內有 indegree, outdegree 介紹 #重要題型 | ||
207 | Course Schedule | BFS (拓樸) | Graph | Python | ||
210 | Course Schedule II | BFS (拓樸) | Graph | Python | ||
[Lint] 892 | Alien Dictionary | BFS (拓樸) |