題目解釋
給定一個字串 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
﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊
致力於打破現有框架的 AI 藝術創作者，曾接受藝文雜誌的個人專訪，作品於香港實體展出。有擔任大學講座講師與 Stable Diffusion AI 年會講者的經驗。擅長 Live Prompting，曾獲 GIGABYTE VS AI 街頭對戰冠軍、ASUS 校園 AI 繪圖競賽亞軍等殊榮。
---
歡迎合作邀約 / 委託 / 各式交流
ᴇᴍᴀɪʟ：dpys@techmagichouse.art
- [推薦工具] 讓程式碼截圖變的美美的吧！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
