424. Longest Repeating Character Replacement

Quick Identifier

• Topic: sliding-window
• Pattern: Sliding Window (Variable Window with "Budget" + Frequency Map)
• Hint: At most k character replacements. The validity of a window is defined by: (length of window) - (count of most frequent character in window) <= k.
• Difficulty: Medium
• Companies: Google, Amazon, Meta, Bloomberg, Apple
• LeetCode: 424

Quick Sights

• Time Complexity: O(n). The right pointer iterates through the string exactly once. The left pointer only moves forward. Updating and checking the frequency array takes $O(1)$ time because the alphabet size is bounded (26 uppercase letters).
• Space Complexity: O(1). We only need an array of size 26 to store character frequencies.
• Core Mechanism: As you expand the sliding window, track the maximum frequency (maxFreq) of any single character currently in the window. The number of characters you need to replace to make the whole window uniform is simply the window's size minus maxFreq. If this difference exceeds k, the window is invalid and must be shrunk from the left.

Concept Explanation

As a senior engineer, the leap in logic here is realizing you do not need to know which character you are replacing to. You only care about the majority character in your current frame.

Imagine you have a frame over a sequence of letters. You want to make them all identical.

1. Identify the Champion: In your current frame, one letter appears more often than any other. Let's call its frequency the maxFreq.
2. The Replacement Math: To make every letter in the frame match the Champion, you must replace every other letter. How many is that? It's exactly windowSize - maxFreq.
3. The Budget Check: You are only allowed k replacements. Therefore, if windowSize - maxFreq <= k, your frame is perfectly valid.
4. The Stale Max Frequency Trick: When your frame becomes invalid (you need too many replacements), you slide the left edge forward. You decrement the frequency of the letter that dropped out. However, you do not strictly need to rescan the array to find the new maxFreq. Why? Because we only care about finding a longer valid window than our current best. A longer window can only be formed if we find a new historical maximum frequency. Thus, allowing maxFreq to remain "stale" (artificially high) during the shrinking phase doesn't break the search for the global maximum length.

Diagram

This flowchart highlights the sliding window logic utilizing the stale maxFreq optimization.

Study Pattern (SDE3+)

• 0–3 min: Write down the core inequality: windowLen - maxFreq <= k. Explain that maxFreq represents the "free" characters we don't have to change.
• Implementation pass: Implement the O(1) space frequency array (size 26). Clearly articulate the "stale maxFreq" trick to the interviewer—it proves deep understanding of sliding window bounds.
• 5 min extension: What if the string contained arbitrary Unicode characters? You would swap the size-26 array for a Hash Map. Updating maxFreq stays $O(1)$, but if you chose not to use the stale maxFreq trick, shrinking would require iterating the map, increasing complexity to $O(n \cdot |Σ|)$.

Approaches

• Brute force — Check all substrings, count frequencies to find maxFreq, check if valid. Time: $O(n^2)$.
• Strict Sliding Window — On invalid window, shrink left, decrement counts, and strictly rescan the 26-element array to find the true new maxFreq. Time: $O(26 \cdot n) = O(n)$.
• Optimized Sliding Window — Never decrease maxFreq. Only increase it when a character count surpasses the historical maximum. Time: $O(n)$ with lower constant factor. (Always pick this for interviews)

Optimal Solution

Go

func characterReplacement(s string, k int) int {
	counts := make([]int, 26)
	left := 0
	maxFreq := 0
	best := 0

	for right := 0; right < len(s); right++ {
		index := s[right] - 'A'
		counts[index]++

		// Update historical maximum frequency in any window so far
		if counts[index] > maxFreq {
			maxFreq = counts[index]
		}

		// If the characters we need to replace exceeds our budget 'k',
		// the window is invalid and we must shrink it.
		// Note: We use 'if' instead of 'while' because we only need to
		// shift the window rightward once it's invalid, maintaining its size.
		if (right - left + 1) - maxFreq > k {
			counts[s[left]-'A']--
			left++
		} else {
			// Only update best if the window was valid
			width := right - left + 1
			if width > best {
				best = width
			}
		}
	}

	return best
}

JavaScript

function characterReplacement(text, k) {
	const counts = new Array(26).fill(0);
	let left = 0;
	let maxFreq = 0;
	let best = 0;

	for (let right = 0; right < text.length; right++) {
		const index = text.charCodeAt(right) - 65;
		counts[index]++;

		if (counts[index] > maxFreq) {
			maxFreq = counts[index];
		}

		// Invalid window: Need to replace more than 'k' chars
		if ((right - left + 1) - maxFreq > k) {
			const leftIndex = text.charCodeAt(left) - 65;
			counts[leftIndex]--;
			left++; // Shift the window without shrinking its size
		} else {
			const width = right - left + 1;
			if (width > best) {
				best = width;
			}
		}
	}

	return best;
}

Walkthrough

Input: s = "AABABBA", k = 1

(Notice how in steps 4, 5, 6 the window simply "shifts" at a size of 4, never shrinking smaller, waiting to encounter a density that pushes maxFreq to 4).

Output: 4

Edge Cases

• k is equal to or larger than s.length (Returns s.length).
• String has length 1 (Returns 1).
• All characters in the string are identical (Returns s.length).

Pitfalls

• Forgetting that the problem specifically implies uppercase English letters, allowing for a fast size-26 integer array instead of a heavier hash map.
• Getting bogged down trying to decrement maxFreq perfectly when sliding left. It is mathematically unnecessary for finding the maximum length.

Similar Problems

• 1004. Max Consecutive Ones III — Binary array, exact same inequality concept but specifically for zeros.
• 904. Fruit Into Baskets — At most two distinct values.
• 3. Longest Substring Without Repeating — Zero duplicates vs budgeted mismatches.

Mind-Map Tags

#sliding-window #frequency-map #budget #maximize-window #stale-max-trick