Longest Repeating Character Replacement

Mediumstringsliding-windowhash-table
Category: Sliding Window
Companies that ask this question:
AmazonGoogleFacebook
LeetCode →NeetCode →

Approach

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 'B's or vice versa to get "BBBB" or "AAAA"

Example 2:

Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace one 'A' in the middle with 'B' to get "AABBBBA"
The substring "BBBB" has length 4.

Approach: Sliding Window (Optimal)

Intuition

Use a sliding window and track the frequency of characters. The key insight is:

  • Window is valid if: windowLength - maxFrequency <= k
  • Where maxFrequency is the count of the most frequent character in the window
  • This means we need at most k replacements to make all characters the same

Key Formula

replacementsNeeded = windowLength - maxFrequency
If replacementsNeeded <= k, the window is valid

Algorithm

def characterReplacement(s, k):
    count = {}
    maxFreq = 0
    maxLength = 0
    left = 0
    
    for right in range(len(s)):
        # Add right character
        count[s[right]] = count.get(s[right], 0) + 1
        maxFreq = max(maxFreq, count[s[right]])
        
        # Shrink window if invalid
        while (right - left + 1) - maxFreq > k:
            count[s[left]] -= 1
            left += 1
        
        # Update max length
        maxLength = max(maxLength, right - left + 1)
    
    return maxLength

Example Walkthrough

For s = "AABABBA", k = 1:

Window: "A"     → maxFreq=1, length=1, replacements=0 ✓
Window: "AA"    → maxFreq=2, length=2, replacements=0 ✓
Window: "AAB"   → maxFreq=2, length=3, replacements=1 ✓
Window: "AABA"  → maxFreq=3, length=4, replacements=1 ✓
Window: "AABAB" → maxFreq=3, length=5, replacements=2 ✗
  Shrink: "ABAB" → maxFreq=2, length=4, replacements=2 ✗
  Shrink: "BAB"  → maxFreq=2, length=3, replacements=1 ✓
Continue...
Max length: 4

Time Complexity

  • O(n): Each character visited at most twice (once by right, once by left)

Space Complexity

  • O(1): At most 26 characters in the count map

Why This Works

  • We don't need to actually replace characters
  • We only need to check if replacements needed ≤ k
  • The most frequent character tells us the minimum replacements needed
  • Sliding window maintains valid substrings efficiently

Common Mistakes

  1. Not updating maxFreq correctly: Should track overall max, not just current window
  2. Wrong window validity check: Must be windowLength - maxFreq > k
  3. Forgetting to shrink: Must move left pointer when invalid

Solution

java
1/**
2 * Longest Repeating Character Replacement
3 * Time: O(n)
4 * Space: O(1) - at most 26 characters
5 */
6
7import java.util.*;
8
9// Approach: Sliding Window (Optimal)
10class Solution {
11    public int characterReplacement(String s, int k) {
12        int[] count = new int[26];
13        int maxFreq = 0;
14        int maxLength = 0;
15        int left = 0;
16        
17        for (int right = 0; right < s.length(); right++) {
18            // Add right character
19            count[s.charAt(right) - 'A']++;
20            maxFreq = Math.max(maxFreq, count[s.charAt(right) - 'A']);
21            
22            // Shrink window if invalid
23            while ((right - left + 1) - maxFreq > k) {
24                count[s.charAt(left) - 'A']--;
25                left++;
26            }
27            
28            // Update max length
29            maxLength = Math.max(maxLength, right - left + 1);
30        }
31        
32        return maxLength;
33    }
34}
35
36// Alternative: Without while loop
37class Solution2 {
38    public int characterReplacement(String s, int k) {
39        int[] count = new int[26];
40        int maxFreq = 0;
41        int left = 0;
42        
43        for (int right = 0; right < s.length(); right++) {
44            count[s.charAt(right) - 'A']++;
45            maxFreq = Math.max(maxFreq, count[s.charAt(right) - 'A']);
46            
47            if ((right - left + 1) - maxFreq > k) {
48                count[s.charAt(left) - 'A']--;
49                left++;
50            }
51        }
52        
53        return s.length() - left;
54    }
55}
56
Loading visualizer...