Longest Repeating Character Replacement (LC 424)

Pattern: Sliding Window (variable size)
Difficulty: Medium
Key Concept: A window is valid if (window length) - (count of most frequent char) <= k — you only need to replace the “minority” characters.

Problem Statement

You are given a string s and an integer k. You may choose any character of the string and change it to any other uppercase English letter at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

Input

• s: String — uppercase English letters
• k: int — max replacements

Output

• int — maximum achievable length

Example

• s = "ABAB", k = 2 → 4
• s = "AABABBA", k = 1 → 4

---

1. Algorithm & Pseudocode

Brute force

For every substring, count letter frequencies, check if length - maxFreq <= k, take maximum length.

best = 0
for left from 0 to n-1:
    freq[26] = zeros
    for right from left to n-1:
        update freq for s[right]
        maxFreq = max(freq)
        if (right-left+1) - maxFreq <= k:
            best = max(best, right-left+1)
return best

Optimal

Expand right, maintain freq in the window and maxFreq (largest count seen so far in the window—see analysis). While invalid, shrink left.

freq[26] = 0
left = 0
maxFreq = 0
best = 0
for right from 0 to n-1:
    freq[s[right]]++
    maxFreq = max(maxFreq, freq[s[right]])
    while (right-left+1) - maxFreq > k:
        freq[s[left]]--
        left++
    best = max(best, right-left+1)
return best

---

2. Step-by-Step Analysis (Beginner-Friendly)

1. What “replacements needed” means If the most common character in a window appears maxFreq times, the other windowLen - maxFreq characters must be flipped to match it. That must be <= k.

2. Why we do not recompute true maxFreq after shrinking When left moves, the real most frequent count might drop, but using a stale maxFreq only makes (windowLen - maxFreq) look larger than reality—so we might shrink more than strictly necessary. That never produces an overly long invalid answer; best still records valid peaks. (This is the standard O(n) trick.)

3. Why sliding window As right grows, if the window becomes invalid, increasing left is the only way to reduce windowLen or drop a minority character count.

4. Uppercase only Fixed 26-size frequency array.

---

3. The Dry Run

Sample: s = "AABAB", k = 1.

right	add	window	freq snapshot (A,B)	maxFreq	len-max	action	best
0	A	A	(1,0)	1	0	OK	1
1	A	AA	(2,0)	2	0	OK	2
2	B	AAB	(2,1)	2	1	OK	3
3	A	AABA	(3,1)	3	1	OK	4
4	B	AABAB	(3,2)	3	2	>k	shrink…

Shrink left until valid:

• Remove s[0]='A': window ABAB → (2,2), maxFreq stale=3 still; len-max=4-3=1 OK → best=4.

Result: 4.

ASCII

k=1: need at most one "odd" char out in the window

A A B A B
L       R  invalid (need 2 changes to make all same)
  L     R  valid window length 4

---

4. Java Solution

Brute Force

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

Time: O(n²).
Space: O(1) — 26 counters.

Optimal

class Solution {
    public int characterReplacement(String s, int k) {
        int[] freq = new int[26];
        int left = 0;
        int maxFreq = 0;
        int best = 0;
        for (int right = 0; right < s.length(); right++) {
            int idx = s.charAt(right) - 'A';
            freq[idx]++;
            maxFreq = Math.max(maxFreq, freq[idx]);
            while (right - left + 1 - maxFreq > k) {
                freq[s.charAt(left) - 'A']--;
                left++;
            }
            best = Math.max(best, right - left + 1);
        }
        return best;
    }
}

Time: O(n) — each index enters/leaves window once.
Space: O(1).

---

5. The “Java vs. Others” Edge

• char - 'A' Maps 'A'..'Z' to 0..25; fails silently if input were lowercase—problem guarantees uppercase.
• Stale maxFreq Interviewers often probe this; explain why the answer remains correct.
• Python Same logic with collections.defaultdict(int); Java’s int[26] is zero-allocation hot path.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	O(n²)	O(1)	Recompute maxFreq per inner window.
Sliding window	O(n)	O(1)	Stale maxFreq trick; 26-letter array.