You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

Example 1:

Input: s = “ABAB”, k = 2 Output: 4 Explanation: Replace the two ‘A’s with two ‘B’s or vice versa. Example 2:

Input: s = “AABABBA”, k = 1 Output: 4 Explanation: Replace the one ‘A’ in the middle with ‘B’ and form “AABBBBA”. The substring “BBBB” has the longest repeating letters, which is 4. There may exists other ways to achieve this answer too.

解題思路:

AABAB k=1 我們肉眼可以直接看出，把第三個 B 換成 A 就可以得到最長的字串。 但用程式碼就需要思考一下，簡單的方式遍歷這些字串，

  1. 字典的方式紀錄所經過的字元，都把他們的數量給記下來
  2. 在這字典中找出出現最多的字串作為我們的最大值
  3. 最大值以外的值就是我們要把更改的字元，這必須小於k次
  4. 如果最大值以外的直超過k了，那就只能把最舊的字串給移除

AABAB k=1

遍歷到第四個A時

{
    'A': 3,
    'B': 1
}

這時候可以發現 B 需要翻轉一次

當遍歷到最後的時候

{
    'A': 3,
    'B': 2
}

我們發現 B 需要翻轉兩次，這時候就要把最舊的字串給移除，也就是 A，這樣就可以得到最長的字串。

{
    'A': 2,
    'B': 2
}

這還沒有滿足 k=1 的條件，所以我們要繼續移除舊的字串直到滿足為止。

Code Example


def characterReplacement(s, k):
    word_to_count = {}
    left = 0
    max_length = 0

    for right in range(0, len(s)):
        current_word = s[right]
        if current_word not in word_to_count.keys():
            word_to_count[current_word] = 1
        else:
            word_to_count[current_word] += 1

        total_count = 0
        max_word_count = 0
        for key in word_to_count.keys():
            total_count += word_to_count[key]
            max_word_count = max(max_word_count, word_to_count[key])
        

        while (total_count - max_word_count) > k:
            left_current_word = s[left]
            word_to_count[left_current_word] -= 1
            total_count = 0
            max_word_count = 0

            for key in word_to_count.keys():
                total_count += word_to_count[key]
                max_word_count = max(max_word_count, word_to_count[key])
            left += 1
        max_length = max(max_length, total_count)

    return max_length