LeetEye LeetEye
Medium Sliding Window ~5 min

Longest Repeating Character Replacement

sliding-window 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.

Examples

Example 1
Input: s = "ABAB", k = 2
Output: 4
Replace the two 'A's with 'B's or vice versa.
Example 2
Input: s = "AABABBA", k = 1
Output: 4
Replace the 'B' at index 2 with 'A'. Substring "AAAB" or replace 'A' at index 0 with 'B' for "BABBA" → "BBBB" (substring "ABBB" starting at 1).
Key Insight

Characters to replace = window size - count of most frequent character.

Valid window: size - max_frequency ≤ k. Expand right, shrink left when invalid, track max size.

How to Approach This Problem

Pattern Recognition: When you see keywords like longest repeating character replacement sliding-window, think Sliding Window.

Step-by-Step Reasoning

1 A window can become all same character if:
Answer: Characters to change ≤ k
We have k changes. If we need more than k, window is invalid.
2 In a valid window, which character should we NOT change?
Answer: The most frequent character
Keeping the most frequent minimizes changes needed. Changing the minority to match the majority.
3 For a window of size W with most frequent character appearing F times: Replacements needed = ?
Answer: W - F
Total chars - chars we keep = chars we must change.
4 Window is invalid when:
Answer: W - F > k
If we need more than k replacements, we can't make all chars the same.
5 When window becomes invalid, we:
Answer: Move left pointer right by 1
Shrink window minimally. Maybe removing one char from left makes it valid again.
6 To know the most frequent character in current window:
Answer: Keep a frequency map of chars in window
Maintain count of each character. Update as window expands/shrinks.

Solution

def characterReplacement(s: str, k: int) -> int:
    count = {}  # Frequency of chars in window
    left = 0
    max_freq = 0
    max_len = 0
    
    for right in range(len(s)):
        count[s[right]] = count.get(s[right], 0) + 1
        max_freq = max(max_freq, count[s[right]])
        
        # Window is invalid: size - max_freq > k
        while (right - left + 1) - max_freq > k:
            count[s[left]] -= 1
            left += 1
        
        max_len = max(max_len, right - left + 1)
    
    return max_len

Complexity Analysis

Time O(n)
Space O(26)

Master This Pattern

Build intuition with interactive MCQs. Practice Sliding Window problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye