ETH官方钱包

前往
大廳
主題

LeetCode - 424. Longest Repeating Character Replacement 解題心得

Not In My Back Yard | 2021-10-21 00:00:08 | 巴幣 10 | 人氣 482

題目連結:


題目意譯:
你被給定一字串 s 以及一整數 k。你可以選定字串中任意字元並將其改變為其他任意的大寫英文字元。你最多可以執行此操作 k 次。

回傳執行以上操作後,你所能得到的包含相同字母之最長子字串的長度。

限制:
1 ≦ s.length ≦ 10 ^ 5
s 只由大寫英文字母組成。
0 ≦ k ≦ s.length



範例測資:
範例 1:
輸入: s = "ABAB", k = 2
輸出: 4
解釋: 將兩個 'A' 替換成兩個 'B',或者反過來也可以。

範例 2:
輸入: s = "AABABBA", k = 1
輸出: 4
解釋: 將中間的 'A' 替換為 'B' 形成 "AABBBBA"。
子字串 "BBBB" 有著最長重複字母,其長度為 4。


解題思維:
利用類似於昨天的題目之想法。不過該題只有 0 和 1,而本題有 'A' ~ 'Z'。而我們可以看到每一次操作所變成的字母應為相同的字母,才會使結果盡可能地長。

因此可以窮舉出操作之所有可能的變化:操作統一變成 'A'、統一變成 'B'……等等,然後看哪種操作可以得到最長的相同字母子字串。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作