LeetCode 424. Longest Repeating Character Replacement

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 achive this answer too.

---

Solution

from collections import defaultdict

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        left = 0
        right = 0
        frequency = defaultdict(int)
        max_count = 0

        for _ in range(len(s)):
            frequency[s[right]] += 1
            max_count = max(max_count, frequency[s[right]])
            if right - left + 1 - max_count > k:
                frequency[s[left]] -= 1
                left += 1

            right += 1

        return right - left