Longest Repeating Character Replacement#

Given a string of uppercase letters and a number k, you may replace at most k characters with any other uppercase letter. Find the length of the longest substring made of a single repeated character that you can produce after those replacements.

Example#

Input: s = "AABABBA", k = 1 Output: 4. Changing one character in “ABAB” yields “AAAA” or similar, giving a run of length 4.

Brute force#

Try every substring, count its most frequent character, and check whether the remaining characters (window length minus that count) can be replaced within k. Keep the longest valid substring. Enumerating substrings is quadratic.

• Time: O(n^2).
• Space: O(1) or O(26) for counts.

Optimal approach#

Slide a window and keep a count of each character inside it. A window is valid when its length minus the count of its most frequent character is at most k, because those extra characters can be replaced. Grow the right edge each step. If the window becomes invalid, shift the left edge forward once. The window never shrinks below the best length found, so the answer is the maximum width reached.

Python solution#

 1from collections import defaultdict
 2
 3
 4def character_replacement(s, k):
 5    counts = defaultdict(int)
 6    left = 0
 7    max_freq = 0
 8    best = 0
 9    for right, ch in enumerate(s):
10        counts[ch] += 1
11        max_freq = max(max_freq, counts[ch])
12        while (right - left + 1) - max_freq > k:
13            counts[s[left]] -= 1
14            left += 1
15        best = max(best, right - left + 1)
16    return best

Complexity#

• Time: O(n), each character is added and removed at most once.
• Space: O(1), the count map holds at most 26 letters.

This problem is a strong drill for the sliding window technique. Keep building with the 60-day challenge.