The problem
Given a string of capital letters and a number k, you may change up to k letters into any other letter. What is the length of the longest stretch you can make where all letters are the same?
Input: s = "AABABBA", k = 1 Output: 4 (repaint the B in "AABA" to get "AAAA")
Picture it
Picture a fence of coloured planks and a small can of paint that can repaint k planks. Inside a window of planks, the cheapest plan is to keep the most common colour and repaint everything else. If “window length − most common count” is more than k, we don’t have enough paint, so we slide the left edge forward.
How to recognise it
- The answer is the longest contiguous stretch that satisfies a rule, so think sliding window.
- The rule is "at most k letters need changing". In a window, the cheapest fix keeps the most common letter and changes the rest: (window length) − (top count) changes.
- The rule is monotone: if a window needs more than k changes, any bigger window containing it does too. So you can grow on the right and shrink on the left.
- Up to 10^5 capital letters, so checking every substring is too slow.
Start with brute force
From every start, extend to the right, keep letter counts, and record the window whenever it needs at most k changes.
from collections import Counter
def character_replacement_brute(s, k):
best = 0
for i in range(len(s)):
count = Counter()
for j in range(i, len(s)):
count[s[j]] += 1
if (j - i + 1) - max(count.values()) <= k:
best = max(best, j - i + 1)
return best
There are about n²/2 windows, and each check scans up to 26 counts, so time is O(26 · n²). With n = 10^5 that is over 10^11 steps. Space is O(1), as at most 26 letters are counted.
From brute force to the idea
- Find the waste. Each start rebuilds its counts from nothing, even though neighbouring windows share almost every letter.
- Slide one window. Move
rightone letter at a time and add it tocount. If the window needs more than k changes, drop letters from the left until it does not. - Track the top count cheaply.
topis the highest count any letter has reached. Updating it with the letter that just entered is O(1), instead of scanning 26 counts. - Never lower
top. When letters leave,topmay now be too high for the current window. That is safe: the window can then only be as long astop + k, a length already achieved by a real valid window.bestonly grows when some letter reaches a new, higher count. - Record after shrinking. The window
right - left + 1is a candidate on every step.
This is the key idea: a window whose length minus its top letter count must stay at most k, with the top count only ever going up.
The key idea
A window is fine while (length − count of its most frequent letter) ≤ k. Grow right, shrink left when it breaks. O(n).
Python solution
def character_replacement(s, k):
count, left, top, best = Counter(), 0, 0, 0
for right, ch in enumerate(s):
count[ch] += 1
top = max(top, count[ch]) # most common colour in window
while (right - left + 1) - top > k: # too many planks to repaint
count[s[left]] -= 1
left += 1
best = max(best, right - left + 1)
return bestLeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import Counter
In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(26 · n²): every window, each with a scan of the counts | O(1): at most 26 counts |
| Sliding window (shown code) | O(n): right and left each move forward at most n times | O(1): at most 26 counts |
Edge cases
- k = 0 (
"AAAB"): returns 3, the longest run of one letter. - k at least the length (
"ABC", k = 5): returns 3, the whole string. - Example (
"AABABBA", k = 1): returns 4. - All different, k = 0 (
"ABCD"): returns 1. - Empty string: returns 0. LeetCode guarantees at least one letter.
- Missing import: the code needs
from collections import Counter; without it the call raisesNameError.
Common mistakes
- Recomputing
max(count.values())on every step. Correct, but 26 times more work per step; the staletopis enough. - Lowering
topwhen letters leave and then trying to keep it exact, which is complicated and unnecessary. - Comparing the number of distinct letters with k, instead of the number of letters that are not the most common one.
- Worrying that the
whileshould be anif. Both give the same answer here: the window grows by one per step andtopnever falls, so one step left always restores the rule.
Given a list of 0s and 1s and a number k, return the longest stretch of 1s you can get by flipping at most k zeros. For [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0] with k = 2 the answer is 6. Describe your approach, then write it if you like.
Compare with our answer
This is the same problem with only two "letters", where you always keep 1. So the number of changes is simply the number of zeros in the window. Grow on the right, count zeros, and shrink from the left while there are more than k.
def longest_ones(nums, k):
left = zeros = best = 0
for right, x in enumerate(nums):
zeros += x == 0
while zeros > k:
zeros -= nums[left] == 0
left += 1
best = max(best, right - left + 1)
return best
No top is needed, because the letter you keep is fixed. Time O(n), space O(1).
A strong answer mentions: that the zero count is the number of changes, shrinking while it exceeds k, and why each element enters and leaves the window once.
1. Fence planks have colours given as integers up to 10^9. Find the longest run of planks you can make one colour by repainting at most k of them. Which approach fits best?
It is the same problem with a bigger alphabet: a dictionary of counts replaces the 26 letters, and the window still grows and shrinks. Sorting destroys contiguity, and trying every start and end is O(n²).
2. Why is the shown code O(n) rather than O(26 · n)?
Each step compares one count with top instead of taking the maximum over all 26 counts. The while loop can run on many steps; it is the total number of moves of left that is at most n.
3. A learner changes while to if in the shown code. What happens?
Each step adds one letter and top never falls, so the window is at most one letter too long, and one step left fixes it. Running both versions on random inputs gives identical answers.
Score 60% or more and the lesson is marked complete.