LeetCode · #424

Longest Repeating Character Replacement Solution

Given a string s and an integer k, find the length of the longest substring you can get by replacing at most k characters.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #424

🏗️

Pattern

Sliding Window — variable size

You are given a string s consisting of uppercase English letters, and an integer k. You can choose any character and change it to any other uppercase letter. You can perform this operation at most k times. Return the length of the longest substring containing the same letter after performing at most k replacements.

Example 1

 Input: s = "ABAB", k = 2 Output: 4 // Replace both 'A's with 'B' (or vice versa) → "BBBB" or "AAAA" 

Example 2

 Input: s = "AABABBA", k = 1 Output: 4 // Replace s[3]='B' → "AAAABBA" — substring "AAAA" has length 4 

Constraints

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

Section Two · Approach 1

Brute Force — O(26·n²)

For each possible substring, count the most frequent character. If length - maxFreq ≤ k, the substring is valid (we can replace the minority characters). Check all substrings and track the longest valid one.

Problem: O(n²) substrings, each needing a frequency count. A sliding window maintains frequency counts incrementally, expanding right and shrinking left when the window becomes invalid — bringing it to O(n).

Java — Brute Force

 class Solution {
public int characterReplacement(String s, int k) {
int max = 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)
                    max = Math.max(max, j - i + 1);
            }
        }
return max;
    }
}

Python — Brute Force

 class Solution:
def characterReplacement(self, s: str, k: int) -> int:
        max_len = 0 for i in range(len(s)):
            count = {}
            max_freq = 0 for j in range(i, len(s)):
                count[s[j]] = count.get(s[j], 0) + 1
max_freq = max(max_freq, count[s[j]])
if (j - i + 1) - max_freq <= k:
                    max_len = max(max_len, j - i + 1)
return max_len

Metric	Value
Time	O(n²)
Space	O(1) — 26-slot array

Section Three · Approach 2

Sliding Window — O(n)

Maintain a window [left, right] with a frequency array. Track maxFreq — the count of the most frequent character in the window. The window is valid when windowSize - maxFreq ≤ k (we can replace the non-dominant characters). When invalid, shrink from the left.

💡 Mental model: You have a paint roller that can cover k wrong-colored tiles. Stretch the roller rightward over the wall. As long as the number of tiles that don't match the most common color is ≤ k, the roller works. When too many mismatches appear, slide the left end forward to reduce them.

Algorithm

Step 1: left = 0, maxFreq = 0, frequency array count[26].
Step 2: For each right: increment count[s[right]], update maxFreq.
Step 3: While (right - left + 1) - maxFreq > k: decrement count[s[left]], left++.
Step 4: Update result = max(result, right - left + 1).

🎯 Key insight — maxFreq never needs to decrease:

We only care about the largest valid window.
If maxFreq decreases (because the frequent char left the window), the window can't be larger than the previous best anyway.
So we don't need to recompute the true max frequency after shrinking — we only update maxFreq when it increases.
This is what makes the algorithm O(n) instead of O(26n).

Section Four · Trace

Visual Walkthrough

Trace through s = "AABABBA", k = 1:

Sliding Window — expand right, shrink left when replacements > k

Section Five · Implementation

Code — Java & Python

Java — Sliding Window

 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']++;
            maxFreq = Math.max(maxFreq, count[s.charAt(right) - 'A']);
while (right - left + 1 - maxFreq > k) {
                count[s.charAt(left) - 'A']--;
                left++;
            }

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

Python — Sliding Window

 class Solution:
def characterReplacement(self, s: str, k: int) -> int:
        count = {}
        left = max_freq = result = 0 for right in range(len(s)):
            count[s[right]] = count.get(s[right], 0) + 1
max_freq = max(max_freq, count[s[right]])
while (right - left + 1) - max_freq > k:
                count[s[left]] -= 1
left += 1
result = max(result, right - left + 1)
return result

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Brute Force	O(n²)	O(1)	Check all substrings
Sliding Window ← optimal	O(n)	O(1)	26-slot array; each char enters/leaves window once

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
k ≥ n	`"ABC", k=3`	Can replace everything → answer is n.
k = 0	`"AABBA", k=0`	No replacements — find longest run of same char. "AA" → 2.
All same	`"AAAA", k=2`	Already uniform — answer is n.
Single char	`"A", k=0`	Trivial — answer is 1.
Alternating	`"ABABAB", k=2`	Can make "AAAAAB" → 5 or similar. Window expands to 5.

⚠ Common Mistake: Recomputing maxFreq by scanning the entire frequency array after each left-shrink. This is unnecessary — maxFreq only needs to increase for larger windows to beat the current best. Leaving it at its historical max is both correct and faster.

← Back to Sliding Window problems

LearningTree

LC 424 · Longest Repeating Character Replacement — Solution & Explanation | DSA Guide