題目解釋
給定一個字串 s
和一個整數 k
。您可以選擇字串中的任何字元並將其變更為任何其他大寫英文字元。
您最多可以執行此操作 k
次。 傳回執行上述操作後所得到的包含相同字母的最長子字串的長度。
範例
- 輸入:
s = "ABAB", k = 2
- 輸出:
4
輸出是 4
,因為如果我們把 s
換成 "AAAA"
或是 "BBBB"
,最長的 substring 的長度就是 4
。
最佳解法
由於這題是需要在 k
的容許範圍內替換掉字母,以讓整個 substring 的字串能夠盡可能變長。因此我們直覺的就想到建立一個 {字母: 次數}
的 dict 來維護我們 traverse 時的關係。
我們使用雙指標(Two Pointer)的解法來解這題。
NOTE: 請謹記 right - left + 1
這個公式,它就是我們滑動窗口(Sliding Window)的長度!
步驟
在這個 Sliding Window 裡面的所有 character 中,出現最多次的 character 次數是 max_appeared_time
。這個次數決定了我們是否需要縮小窗口。
如果在這個滑動窗口裡面的 character 總數(即 right - left + 1
)減去 max_appeared_time
的結果在替換容許值 k
以內 (<
) ,這代表我們可以在這個範圍內替換最多 k
個字符以讓所有 character 相同。因此,這個 Sliding Window 就是包含相同 character 的最長子字串。
相反的,如果這個 Sliding Window 裡面的 character 總數減去 max_appeared_time
的結果超過 (>
) 替換容許值 k
。
我們就需要調整 left
的位置以縮小 Sliding Window,直到 Sliding Window 內 character 總數減去 max_appeared_time
的結果在 k
的範圍內。
最後,我們再回傳 traverse 歷史中最大的 window size 即可。
程式碼
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
appeared_times = dict()
max_appeared_time = 0
max_window_size = 0
left = 0
for right in range(len(s)):
if s[right] not in appeared_times:
appeared_times[s[right]] = 1
else:
appeared_times[s[right]] += 1
max_appeared_time = max(appeared_times[s[right]], max_appeared_time)
while (right - left + 1) - max_appeared_time > k:
appeared_times[s[left]] -= 1
left += 1
max_window_size = max(right - left + 1, max_window_size)
return max_window_size
時間複雜度
O(n)
,n 是 s
的字母個數。
空間複雜度
O(n)
。
結語
下次一定會記得怎麼寫 : D
- [推薦工具] 讓程式碼截圖變的美美的吧!VScode CodeSnap 與 3 種同功能線上工具介紹 - 2025-01-05
- [AI 繪圖初級教學] 用 X/Y/Z Plot 比較 Stable Diffusion 的 prompt 與 LoRA 效果 - 2024-12-27
- [AI 繪圖中級篇教學] Stable Diffusion WebUI WD14 Tagger 介紹 - 2024-12-26