LeetCode #424 Medium

Longest Repeating Character Replacement

You may change at most k characters of s to any other uppercase letter. Return the length of the longest substring consisting of a single repeated character that you can produce.

sliding-windowstringshashing

Open on LeetCode ↗

02

Intuition

💡

Ask what it costs to make a given window uniform. Keep whichever character already appears most often and change everything else, so the cost is window length - count of the most frequent character. The window is usable when that cost is at most k. That gives a clean validity test, and since shrinking a window never increases its cost, the standard grow-right / shrink-left sliding window applies.

03

Approach

1

Turn 'at most k replacements' into a window condition

For any substring, the cheapest way to make it uniform is to preserve its most common character and rewrite the rest. If the window has length L and its most frequent character appears maxFreq times, the number of replacements needed is L - maxFreq. So the window is achievable exactly when L - maxFreq <= k. This single inequality is the whole problem.

2

Grow right, shrink left when the cost exceeds k

Advance the right edge one character at a time, updating a frequency map. After each addition, check the cost. If it exceeds k, advance the left edge — decrementing frequencies as characters leave — until the window is valid again. Record the length after each step. Both pointers only move forward, so despite the nested loop the total work is O(n).

3

Note the maxFreq subtlety

Many implementations never decrease maxFreq when shrinking, which looks like a bug but is not: a stale, too-large maxFreq only makes the window look cheaper than it is, so it can never cause the recorded best to exceed a genuinely achievable length. The window can drift out of true validity, but the answer stays correct because the best length was already achieved earlier. Recomputing maxFreq honestly on shrink is also correct and easier to defend in an interview — with only 26 letters the recomputation is O(26) and does not change the complexity class.

04

Solution & live demo

python

▶1class Solution:
▶2    def characterReplacement(self, s, k):
▶3        count = {}
▶4        left = best = maxFreq = 0
▶5        for right, ch in enumerate(s):
▶6            count[ch] = count.get(ch, 0) + 1
▶7            maxFreq = max(maxFreq, count[ch])
▶8            while (right - left + 1) - maxFreq > k:
▶9                count[s[left]] -= 1
▶10                left += 1
▶11            best = max(best, right - left + 1)
▶12        return best

05

Edge cases

k >= len(s)

Every character can be replaced, so the answer is the whole string length. The cost condition is never violated and the window never shrinks.

k == 0

No replacements allowed, so the answer is the longest run of a single character — which the window finds, since any second distinct character immediately makes the cost 1.

All characters identical

maxFreq equals the window length, so the cost stays 0 and the window spans the whole string.

Single character string

One iteration; the answer is 1.

06

Complexity

Time

O(n)

Space

O(1)

The frequency map holds at most 26 entries. Each pointer advances at most n times, so the nested while loop does not make this quadratic.