You are given a string s of uppercase English letters and a number k. You may change up to k characters in the string, each to any other uppercase letter. Return the length of the longest stretch of the string that you can turn into one letter repeated.
s = "ABAB", k = 2 → 4 (change both A's to B: "BBBB")s = "AABABBA", k = 1 → 4 (take "AABA" and change the B: "AAAA")
The string has up to 100,000 letters, and k is between 0 and the string's length.
Take any stretch of the string. How many changes does it need to become one repeated letter?
The cheapest plan is always the same. Keep the letter that already appears most often in the stretch, and change every other letter to it. So if the stretch has length L, and its most common letter appears \text{maxCount} times, it needs:
\text{changes needed} = L - \text{maxCount}
Read it as "the length of the stretch, minus how many times its most common letter appears". For "AABA", L = 4 and A appears 3 times, so it needs 4 - 3 = 1 change.
So the real question is: what is the longest stretch where L - \text{maxCount} \le k? That is a sliding window with a condition, exactly like 4.6.2.
Think of a group of children who must all wear the same colour of shirt, and you can afford k new shirts. In a group where 5 wear red, 2 wear blue and 1 wears green, you keep red and buy 3 red shirts. If you can only afford 2, this group is too big. Someone has to leave the group, from the left end, until the shirts you need fit your budget.
Try every stretch, count its letters, and check the condition.
python
def characterReplacement(s, k): best = 0 n = len(s) for i in range(n): count = [0] * 26 for j in range(i, n): count[ord(s[j]) - ord('A')] += 1 if (j - i + 1) - max(count) <= k: best = max(best, j - i + 1) return best
This is O(n^2 \cdot 26), far too slow for 100,000 letters.
The waste in one sentence: every time the start i moves by one, the brute force recounts a stretch that differs from the previous one by a single letter.
(1) count = {}. How many times each letter appears inside the window.
(2) max_count = 0. The biggest count of any one letter we have seen in a window. Read the section after this one carefully, because this number behaves in a surprising way.
(3) Move the right edge forward, one letter per turn.
(4) Count the new letter.count.get(s[right], 0) means "the current count, or 0 if this letter is not in the map yet". Then we add 1.
(5) Update max_count. Only the letter that just arrived could have a new, bigger count, so we only need to compare with that one.
(6) Does the window need too many changes?right - left + 1 is the window's length L. L - max_count is the number of changes needed. If that is more than k, the window is not allowed.
(7) Shrink from the left. The leftmost letter leaves the window, so its count drops by one, and left moves forward.
(8) Record the length. After the repair, the window is allowed, so its length is a candidate answer.
Look at line (7). When a letter leaves the window, its count goes down. But max_count is never lowered. So after shrinking, max_count may be bigger than the real top count in the window. The code carries an out-of-date number on purpose. Surprisingly, the answer is still correct. Here is why.
The answer best only grows when we find a window longer than every window before it.
A longer allowed window needs L - \text{maxCount} \le k with a bigger L. With k fixed, a bigger L needs a biggermaxCount than any window before.
Now suppose max_count is out of date and too big. Then the check in line (6) is too gentle, and a window may stay larger than it should. But that window is never longer than best already is, because max_count was reached by an earlier window, and best already counted that window's length. So best does not wrongly grow.
The moment a truly better window appears, its top letter really does reach a bigger count. Line (5) updates max_count to that real value, and best grows correctly.
So the stale number can only fail to shrink windows that could never have beaten the answer anyway. Two things follow from this.
The window never becomes shorter than the best length found so far. It slides along the string like a ruler, sometimes growing, never shrinking below the record.
The value in max_count is not always the true top count of the current window. It is a "highest so far" mark. That is fine here, but it would be wrong if the problem asked you to report the top count.
If this feels uneasy, there is an honest version. Recompute the true top count inside the while condition with max(count.values()). That scans at most 26 letters each time, so it is still O(26n) = O(n), and it is easier to defend. Many strong candidates write that version on purpose.
The answer is 4. Notice that the window length stays at 4 from step 3 onward. It slides, but never shrinks below the record. That is the ruler behaviour described above.
Time.right moves forward n times. left only moves forward and never passes right, so it moves at most n times in total over the whole run. Each move does constant work on the map. So the total is O(n), even though there is a while inside the for.
Space. The map holds at most 26 letters. That is a fixed size, so the space is O(1).
This is the "at most k of something" window, one of the two most common window conditions.
Max Consecutive Ones III. A list of 0s and 1s. You may flip up to k zeros. Find the longest run of 1s. Shrink while the window holds more than k zeros. That problem is this one with only two letters, which is a good test of whether you understood this page.
Longest substring with at most k different characters. Shrink while the map has more than k keys.
Longest stretch with sum at most k, when all numbers are zero or more. Shrink while the sum is too big.
That last one comes with a condition you must check before using any window: shrinking must always make the window closer to allowed. With numbers that are zero or more, removing a number can never raise the sum, so shrinking always helps. If negative numbers are allowed, removing one raises the sum, and the window method breaks. Then you need running totals with a hash map instead.
"Why is the condition length - maxCount <= k?" Keep the most common letter and change the rest. Keeping any other letter would mean changing more.
"You never lower max_count. Is that a bug?" This is the question this problem exists to ask. Give the argument above: a stale value can only fail to shrink a window that could never beat the answer.
"What if the string could hold any character, not just 26 letters?" The map still works. Only the space changes, to O(m) for m different characters.
"What if you had to return the actual stretch?" Save left whenever best grows, then slice at the end.
One thing to volunteer: mention that this is Max Consecutive Ones III with a 26-letter alphabet. Seeing that two problems that look different are the same is a strong signal.