Longest Repeating Character Replacement (LeetCode 424)

The problem

You get an uppercase string s and an integer k. You may change up to k characters to any other uppercase letter. Return the length of the longest substring that can be made of a single repeated letter.

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

Take the window "BABB" (indices 2 to 5) and change its single A to B, giving "BBBB", length 4. No length-5 window can be fixed with one change.

How to think about it

Start with brute force. For every substring, count its most common letter. The rest of the letters must be replaced, so the substring works if length − maxCount ≤ k. Trying all O(n²) substrings, even with running counts, is O(n²).

The key insight: the validity rule is a budget. For a window, the cheapest fix is to keep its most frequent letter and change everything else. So a window is valid exactly when (window length) − (count of its most frequent letter) ≤ k. That’s a condition you can check in O(1) as the window grows, and repair by shrinking from the left. That’s the variable sliding window.

A subtle trick: maxf never needs to go down. The code keeps maxf, the highest single-letter count seen in any window so far, and doesn’t lower it when the window shrinks. Why is that safe? The answer can only improve when some window has a bigger maxf than before. A stale, too-high maxf might let an invalid window survive, but such a window is never longer than the best valid one already recorded, because the window only shifts (grows by one, shrinks by one) in that state. So the answer stays correct, and you avoid rescanning all 26 counts.

Which pattern is this? A variable-size sliding window with a frequency map. The tell is “longest substring where at most k things are wrong”.

Approach

1. Keep cnt (letter counts in the window), start = 0, maxf = 0, best = 0.
2. For each i, add s[i] to cnt and update maxf.
3. If (i - start + 1) - maxf > k, the window is over budget: remove s[start] from cnt and move start right by one.
4. Update best with the current window length.
5. Return best.

Solution

from collections import defaultdict

def char_replacement(s, k):
    cnt = defaultdict(int); start = 0; best = 0; maxf = 0
    for i, c in enumerate(s):
        cnt[c] += 1; maxf = max(maxf, cnt[c])          # top count ever seen
        if (i - start + 1) - maxf > k:                  # too many to replace
            cnt[s[start]] -= 1; start += 1              # slide left edge by one
        best = max(best, i - start + 1)
    return best
# char_replacement("AABABBA", 1) -> 4

Dry run

On s = "AABABBA", k = 1:

The answer is 4.

Complexity

• Time: O(n). Each character enters the window once and leaves at most once.
• Space: O(26) = O(1). The count map holds at most 26 letters.

Edge cases and pitfalls

• k = 0: the answer is the longest run of one letter already in s.
• k >= len(s): every window is valid, so the answer is len(s).
• Recomputing maxf on shrink with max(cnt.values()) is also correct and still O(26·n). It’s a fine answer if you can’t justify the stale maxf trick in the interview.
• Using while instead of if to shrink works too here, but if is enough because the window never needs to shrink by more than one step at a time.
• Counting replacements of a fixed target letter misses the point: the letter to keep is whichever is most common in the current window.

Related problems

• Max Consecutive Ones III (LeetCode 1004): the binary version, where the budget is “at most k zeros”.
• Longest Substring Without Repeating Characters (LeetCode 3): the same longest-window template with a different validity rule.
• Fruit Into Baskets (LeetCode 904): a window limited by the number of distinct values.