Longest Repeating Character Replacement

Problem

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.

Constraints:

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

Solution

Approach: Sliding Window with Character Frequency

The key insight is that for a window to be valid, the number of characters we need to replace should not exceed k. In other words: window_size - max_frequency <= k.

We maintain:

char_count: frequency map of characters in the current window
max_count: highest frequency of any single character in the window
left: left boundary of the window

For each character:

Add it to the window and update frequencies
If the window is invalid (too many replacements needed), shrink from the left
Update the maximum window size

Implementation

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        char_count = {}
        left = 0
        max_count = 0
        max_length = 0

        for right in range(len(s)):
            # Add character to window
            char_count[s[right]] = char_count.get(s[right], 0) + 1
            # Update max frequency in current window
            max_count = max(max_count, char_count[s[right]])

            # Window size - most frequent char = characters to replace
            # If this exceeds k, window is invalid
            while (right - left + 1) - max_count > k:
                char_count[s[left]] -= 1
                left += 1

            # Update max length
            max_length = max(max_length, right - left + 1)

        return max_length

Optimized Version (No While Loop):

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        char_count = {}
        left = 0
        max_count = 0

        for right in range(len(s)):
            char_count[s[right]] = char_count.get(s[right], 0) + 1
            max_count = max(max_count, char_count[s[right]])

            # If window is invalid, just move left
            # We don't need to decrease max_count because we only care
            # about finding a longer valid window
            if (right - left + 1) - max_count > k:
                char_count[s[left]] -= 1
                left += 1

        return right - left + 1

Complexity Analysis

Time Complexity: O(n), where n is the length of the string. Each character is processed at most twice.
Space Complexity: O(1), since we only store counts for at most 26 uppercase English letters.

Key Insights

Window Validity: A window is valid if we can replace the non-majority characters (at most k of them) to match the majority character. Formula: window_size - max_frequency <= k.
Max Count Optimization: In the optimized version, we don’t need to decrease max_count when shrinking the window. We only care about finding a window longer than our current best, which requires a higher max_count anyway.
Sliding Window Expansion: We always expand the window with the right pointer. We only shrink when the window becomes invalid.
Greedy Choice: At each step, we greedily try to maximize the window size. The most frequent character in the window is the best candidate to keep, and we replace the others.