Topic · Sliding WindowMedium
Longest Repeating Character Replacement
Understand the problem
Given a string s of only uppercase letters A-Z and an integer k. You may replace at most k characters in the string with any other uppercase letter. Find the length of the longest substring containing a single repeated letter after the replacements.
Examples:
ts
s = "AABABBA", k = 1
output = 4
// The window "AABA" (index 0..3) has three "A" and one "B".
// Replace the one "B" → "AAAA", length 4. With k=1 it cannot get longer.
s = "ABAB", k = 2
output = 4 // replace two "B" → "AAAA"Strategy: a window is valid when the number of characters to replace = (window size − count of the most frequent character) ≤ k.
Basic approach
O(n²) time, O(1) spacets
function characterReplacement(s: string, k: number): number {
let maxLen = 0
for (let i = 0; i < s.length; i++) {
const count = new Array(26).fill(0)
let maxCount = 0
for (let j = i; j < s.length; j++) {
count[s.charCodeAt(j) - 65]++
maxCount = Math.max(maxCount, count[s.charCodeAt(j) - 65])
const windowSize = j - i + 1
if (windowSize - maxCount <= k) maxLen = Math.max(maxLen, windowSize)
else break // over k replacements → stop extending from i
}
}
return maxLen
}Why this approach is slow:
Two nested loops check every substring.
It can be improved because once the window [i..j] is invalid there is no need to expand it further — but you still have to restart from i+1.
Unlock the optimal solution, the step-by-step trace and related questions
See the full step-by-step trace, Big-O and edge cases.