424. Longest Repeating Character Replacement

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

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.

Constraints:

• 1 <= s.length <= 10^5
• s consists of only uppercase English letters.
• 0 <= k <= s.length

Approach

Solution

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        count = {}
        res = 0

        l = 0
        maxF = 0
        for r, c in enumerate(s):
            count[c] = 1 + count.get(c, 0)
            maxF = max(maxF, count[c])

            while (r - l + 1) - maxF > k:
                count[s[l]] -= 1
                l += 1

            res = max(res, r - l + 1)
        return res

Explanation