LeetCode 424. Longest Repeating Character Replacement

justin-jang — Tue, 16 May 2023 13:10:55 +0000

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

DEV Community: justin-jang

LeetCode 424. Longest Repeating Character Replacement

Example 1:

Example 2:

Solution