424. Longest Repeating Character Replacement

At a Glance

• Topic: sliding-window
• Pattern: Sliding Window
• Difficulty: Medium
• Companies: Google, Amazon, Meta, Bloomberg, Apple
• Frequency: High
• LeetCode: 424

Problem (one-liner)

Given a string s and integer k, you may replace at most k characters so that all characters in the window match. Return the length of the longest such substring.

Recognition Cues

• "At most k changes" to make substring uniform
• Window length − max frequency ≤ k must hold for valid window
• Maximize window while maintaining validity

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Approaches

• Brute force — try every window — O(n³) with counting per window.
• Better — sliding window tracking counts — O(n) amortized with frequency array.
• Optimal — grow right; shrink left only when invalid — track maxFreq in window (may be stale but still yields correct max length).

Optimal Solution

Go

func characterReplacement(s string, k int) int {
	count := [26]int{}
	left := 0
	maxFreq := 0
	best := 0
	for right := 0; right < len(s); right++ {
		index := s[right] - 'A'
		count[index]++
		if count[index] > maxFreq {
			maxFreq = count[index]
		}
		width := right - left + 1
		if width-maxFreq > k {
			count[s[left]-'A']--
			left++
			width--
		}
		if width > best {
			best = width
		}
	}
	return best
}

JavaScript

function characterReplacement(text, maxReplacements) {
	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];
		}
		let width = right - left + 1;
		if (width - maxFreq > maxReplacements) {
			counts[text.charCodeAt(left) - 65]--;
			left++;
			width--;
		}
		if (width > best) {
			best = width;
		}
	}
	return best;
}

Walkthrough

Input: s = "AABABBA", k = 1

Grow window while len − maxCharCount ≤ 1; shrink when excess replacements needed.

Invariant: for current [left, right], windowLen - maxFreq is minimum replacements to homogenize to the majority letter in that window.

Edge Cases

• k larger than string length
• Single character string
• All same letter

Pitfalls

• Decrementing maxFreq on shrink — optional fixup is messy; stale maxFreq still works for maximizing length
• Assuming lowercase vs uppercase (problem is uppercase English)

Similar Problems

• 1004. Max Consecutive Ones III — binary array, same inequality idea.
• 904. Fruit Into Baskets — at most two distinct values.
• 3. Longest Substring Without Repeating — zero duplicates vs budgeted mismatches.

Variants

• Cost per character differs — weighted replacements (different objective).
• Minimum replacements to make entire string one character — global frequency.

Mind-Map Tags

#sliding-window #frequency #budget #maximize-window #uppercase-english