0%
Loading ...

【Leetcode 筆記】 424. Longest Repeating Character Replacement

題目解釋

給定一個字串 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

數據女巫 𝔻.𝕡𝕪𝕤 🔮

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

The reCAPTCHA verification period has expired. Please reload the page.