Longest Repeating Character Replacement

1. The obvious way

   Try every substring and count: O(n² x 26).

2. The key insight

   Grow a window to the right, keeping a count per letter and the highest count seen in any window. If window length - highest count exceeds k, the window needs too many repaints: slide it by moving the left edge one step. The highest count never has to shrink, because only a window with a larger highest count can give a longer answer.

3. The algorithm
   1. Counts per letter, left edge at the start, highest count 0.
   2. Add the new letter on the right; update the highest count.
   3. Window length - highest count > k? Remove the left letter and move the left edge on by one.
   4. Best = the largest window length seen.

Watch it run

best 3

def character_replacement(text, k):
    counts = {}
    left = most_common = best = 0
    for right, letter in enumerate(text):
        counts[letter] = counts.get(letter, 0) + 1
        most_common = max(most_common, counts[letter])
        while (right - left + 1) - most_common > k:    # too many planks to repaint
            counts[text[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.