Leetcode - 424. Longest Repeating Character Replacement

Medium

Dec 22, 2025

#sliding-window

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.

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.

1 <= s.length <= 105
s consists of only uppercase English letters.
0 <= k <= s.length

Constraints:

Notes

Intuition

In any window, the minimum replacements needed equals window_length - max_frequency_of_any_char. If this exceeds k, shrink the window. Otherwise, we have a valid window where we can make all characters the same.

Implementation

Maintain a frequency array for 26 characters and track the maximum frequency seen. For each right pointer position, increment the character's frequency and update max frequency. If window_size - max_freq > k, the window is invalid—shrink from the left by decrementing that character's frequency and moving l. Track the maximum valid window length.

Edge-cases

Window size is r - l + 1. The max frequency doesn't need to decrease when shrinking—if it was valid before, using that max won't make the window smaller than it could be.

Time: O(n) — each character processed once
Space: O(1) — frequency array is fixed at 26 elements

Complexity

Solution

class Solution:
    def char2idx(self, c: str) -> int:
        return ord(c) - ord('A')

    def characterReplacement(self, s: str, k: int) -> int:
        freq = [0] * 26  
        l, max_f, max_len = 0, 0, 0
        for r in range(len(s)):
            freq[self.char2idx(s[r])] += 1
            max_f = max(max_f, freq[self.char2idx(s[r])])

            while (r - l + 1) - max_f > k:
                freq[self.char2idx(s[l])] -= 1
                l += 1

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



if __name__ == "__main__":
    # Include one-off tests here or debugging logic that can be run by running this file
    # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
    solution = Solution()