Longest Repeating Character Replacement

Medium

Problem

The string contains uppercase letters. You may replace at most k characters with any letter. Return the length of the longest substring you can make that consists of a single repeated letter.

Example 1

Input:  s = "ABAB", k = 2
Output: 4

Example 2

Input:  s = "AABABBA", k = 1
Output: 4

Replace the A at index 3: "AABBBBA" contains "BBBB".

Test cases

Case 1

Input:    "ABAB", 2
Expected: 4

Case 2

Input:    "AABABBA", 1
Expected: 4

Case 3

Input:    "A", 0
Expected: 1

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Window with max frequency

Time O(n)Space O(26)

A window is valid when length − (count of its most common char) ≤ k. maxFreq never needs to decrease: a smaller one cannot produce a longer answer.

function characterReplacement(s, k) {
const cnt = new Array(26).fill(0);
let l = 0, maxFreq = 0, best = 0;
for (let r = 0; r < s.length; r++) {
maxFreq = Math.max(maxFreq, ++cnt[s.charCodeAt(r) - 65]);
while (r - l + 1 - maxFreq > k) cnt[s.charCodeAt(l++) - 65]--;
best = Math.max(best, r - l + 1);
}
return best;
}