Longest Repeating Character Replacement

Medium#424variable size

You get a string of capital letters and a number k. You may change at most k letters to any other letters. Find the length of the longest piece of one repeated letter you can get. Our example: "ABABBCB" and k = 1 — the answer is 4: change the "A" in "BABB" and get "BBBB".

424 Longest Repeating Character ReplacementWalkthrough · 1×

Example: s = "ABABBCB", k = 1. In the window the letters to change are marked; under the string are the counts, the largest one marked as kept.

0A1B2A3B4B5C6Bcount—
not reached yetwindowletter coming into change, or leavingleft the windowthe letter kept, best window

Start with an empty map: every letter counts 0

01/41
restart · back · play · step
Speed
1function characterReplacement(s, k):
2 count = empty map // missing keys: 0
3 left = 0
4 best = 0
5 for right from 0 to len(s) - 1:
6 count[s[right]] = count[s[right]] + 1
7 while (right - left + 1) - largest(count) > k:
8 count[s[left]] = count[s[left]] - 1
9 left = left + 1
10 best = max(best, right - left + 1)
11 return best
state
count
{}
left
–
right
–
best
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. In a window it is cheapest to keep its most frequent letter and change all the others: that takes the length minus the largest count changes. The window is good when this is at most k.
  2. A good window stays good when it loses a letter from the left, so for each right it is enough to shrink until the window is good again: what is left is the longest good window ending at right.
  3. Shrinking may take more than one step: dropping a letter can lower the largest count, and then the window needs as many changes as before.

Complexity

Time O(26 · n): each letter comes in and leaves once, and the largest count is found among at most 26 counts. Memory O(1): at most 26 counts.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.