245. Longest Repeating Character Replacement

For every possible substring, count the most frequent character and check if the remaining characters can be replaced within k operations.

Brute Force

Enumerate every substring (i, j). For each one, count character frequencies, find the most frequent character count maxFreq, and check if (j - i + 1) - maxFreq <= k. If so, the substring can become all one character with at most k replacements. Track the longest valid one.

This requires O(n^2) substrings and O(26) work per substring to count frequencies, giving O(26 * n^2) = O(n^2) time. Space is O(26) = O(1) for the frequency counter.

Why it's slow: we re-examine overlapping substrings instead of incrementally adjusting a window.

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

Maintain a window [left, right] and track character frequencies inside it. The window is valid when (window_length - max_frequency) <= k, meaning we need at most k replacements. When invalid, shrink from the left.

Mental Model

Imagine a rubber band stretched over a section of the string. The band is "valid" as long as the number of characters that are NOT the most frequent character in that section is at most k (since we'd need to replace each of those). We stretch the band right one character at a time. If stretching makes it invalid, we pull the left end in until it's valid again.

Algorithm Steps

1. Initialize left = 0, max_freq = 0, and a frequency map count for characters in the window.
2. For each right from 0 to n-1: a. Add s[right] to count and update max_freq = max(max_freq, count[s[right]]). b. While (right - left + 1) - max_freq > k, the window has too many characters to replace. Remove s[left] from count and increment left. c. Update best = max(best, right - left + 1).
3. Return best.

Worked Walk-through

Example: s = "AABABBA", k = 1

Answer: 4

Key Insight: max_freq never needs to decrease

A subtle optimization: we never reduce max_freq when shrinking. Why? We only care about finding a LONGER valid window. If max_freq decreased, the window couldn't be longer than our current best anyway. This keeps the algorithm simple and O(n).

Edge Cases

• k >= n: The entire string can be made uniform. Return n.
• All same characters: Every window is valid. Return n.
• k = 0: Return the length of the longest run of identical characters.

Complexity

• Time: O(n) — each character is added and removed from the window at most once.
• Space: O(26) = O(1) — frequency map has at most 26 entries.