Longest Repeating Character Replacement

Problem Description

Given a string s of uppercase letters and an integer k, you can replace any character with any other uppercase letter at most k times. Return the length of the longest substring where all characters are the same after at most k replacements.

Examples

Constraints

• 1 ≤ s.length ≤ 10⁵
• s consists of only uppercase English letters.
• 0 ≤ k ≤ s.length

A Window Is Valid When Its Minority Characters Fit Within k Replacements

The number of replacements needed to make a window uniform is window_size - max_frequency_in_window. If that number exceeds k, the window is invalid and you shrink from the left.

The subtle part: tracking maxFreq. After shrinking the window when the most frequent character leaves, maxFreq might be stale (too high). You could recompute it by scanning the frequency array, but you don’t need to. A stale maxFreq only ever makes you accept windows that are smaller or equal to the best valid window found so far. It never makes you accept an invalid window as valid. So the result is always correct.

Solution 1: Brute Force

For every possible window, count the most frequent character and check if replacements fit within k.

class Solution {
    public int characterReplacement(String s, int k) {
        int result = 0;
        for (int i = 0; i < s.length(); i++) {
            int[] count = new int[26];
            int maxFreq = 0;
            for (int j = i; j < s.length(); j++) {
                count[s.charAt(j) - 'A']++;
                maxFreq = Math.max(maxFreq, count[s.charAt(j) - 'A']);
                if ((j - i + 1) - maxFreq <= k) {
                    result = Math.max(result, j - i + 1);
                }
            }
        }
        return result;
    }
}

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        result = 0
        for i in range(len(s)):
            count = [0] * 26
            max_freq = 0
            for j in range(i, len(s)):
                count[ord(s[j]) - ord('A')] += 1
                max_freq = max(max_freq, count[ord(s[j]) - ord('A')])
                if (j - i + 1) - max_freq <= k:
                    result = max(result, j - i + 1)
        return result

#include <string>
#include <algorithm>

class Solution {
public:
    int characterReplacement(std::string s, int k) {
        int result = 0;
        for (int i = 0; i < s.size(); i++) {
            int count[26] = {}, maxFreq = 0;
            for (int j = i; j < s.size(); j++) {
                maxFreq = std::max(maxFreq, ++count[s[j] - 'A']);
                if ((j - i + 1) - maxFreq <= k)
                    result = std::max(result, j - i + 1);
            }
        }
        return result;
    }
};

Complexity Analysis:

• Time Complexity: O(n²). Two nested loops over the string.
• Space Complexity: O(1). Fixed 26-element count array.

Where it breaks: at n = 10⁵ this doesn’t pass. Move to the sliding window.

Solution 2: Sliding Window with maxFreq Shortcut

Expand the window right, shrink left when replacements exceed k. Track the max frequency seen so far without ever decreasing it.

class Solution {
    public int characterReplacement(String s, int k) {
        int[] count = new int[26];
        int left = 0, maxFreq = 0, result = 0;

        for (int right = 0; right < s.length(); right++) {
            count[s.charAt(right) - 'A']++;
            // only update maxFreq when the new char increases it; never decrease
            maxFreq = Math.max(maxFreq, count[s.charAt(right) - 'A']);

            // shrink window if too many replacements are needed
            if ((right - left + 1) - maxFreq > k) {
                count[s.charAt(left) - 'A']--;
                left++;
            }

            result = Math.max(result, right - left + 1);
        }
        return result;
    }
}

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

        for right in range(len(s)):
            count[s[right]] = count.get(s[right], 0) + 1
            # only update max_freq when the new char increases it; never decrease
            max_freq = max(max_freq, count[s[right]])

            # shrink window if too many replacements are needed
            if (right - left + 1) - max_freq > k:
                count[s[left]] -= 1
                left += 1

            result = max(result, right - left + 1)

        return result

#include <string>
#include <algorithm>

class Solution {
public:
    int characterReplacement(std::string s, int k) {
        int count[26] = {};
        int left = 0, maxFreq = 0, result = 0;

        for (int right = 0; right < s.size(); right++) {
            // only update maxFreq when the new char increases it; never decrease
            maxFreq = std::max(maxFreq, ++count[s[right] - 'A']);

            // shrink window if too many replacements are needed
            if ((right - left + 1) - maxFreq > k) {
                count[s[left++] - 'A']--;
            }

            result = std::max(result, right - left + 1);
        }
        return result;
    }
};

Complexity Analysis:

• Time Complexity: O(n). Each character enters and leaves the window at most once.
• Space Complexity: O(1). Fixed 26-element array regardless of input size.

Where it breaks: if you try to recompute maxFreq by scanning the count array after each shrink, the algorithm still works but costs O(26) = O(1) per step, which is fine. The stale maxFreq trick just avoids even that constant overhead.

Common Mistakes

• Recomputing maxFreq from the count array after shrinking. Not wrong, just unnecessary. The stale maxFreq is safe and simpler.
• Shrinking with a while loop instead of a single if. The window never needs to shrink by more than one position at a time. A while loop is overkill and can give the wrong result because you’re shrinking past the maximum known valid size.
• Forgetting that maxFreq is per-window, not global. If you reset maxFreq = 0 outside the loop and never update it correctly, you’ll get wrong answers on inputs where the dominant character changes mid-string.

Frequently Asked Questions

Why does keeping a stale maxFreq work? The window can only grow by exactly one each step (right advances one position, left stays or advances one). A stale maxFreq means the window stays the same size rather than growing. We never record a window that’s actually invalid as the answer because we only update result = max(result, window_size) after the validity check.

What if k is 0? The window can only contain one distinct character. The algorithm still works: window_size - maxFreq > 0 triggers a shrink whenever a new character appears.

How is this different from “Longest Substring Without Repeating Characters”? Both use sliding windows, but the validity condition differs. This problem allows repeats as long as the minority characters fit within k. The other problem requires zero repeats.

← All Problems