Longest Repeating Character Replacement

def characterReplacement(s, k):
    count = {}
    left = top = best = 0
    for right, ch in enumerate(s):
        count[ch] = count.get(ch, 0) + 1
        top = max(top, count[ch])
        if right - left + 1 - top > k:
            count[s[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

Longest Repeating Character Replacement. Given a string of capital letters and a number k, you may replace up to k letters. Return the length of the longest run of one repeated letter you can make.

With A, B, A, B and k two, replace both B's: four. With A, A, B, A, B, B, A and k one, change the B in A, A, B, A: four again.

The slow way checks every substring: its length minus its most common letter's count is the number of changes it needs. That's n squared substrings.

Instead, slide one window and count its letters. It's fine while its length minus its top count is at most k. Each step, the right edge grows by one; if that needs too many changes, the left edge moves too, so the size holds.

The subtle part: the top count never has to drop. If it's stale and too high, the window can't grow; it only slides at a size that already worked. To grow, a letter's real count must beat the record, so the answer is never inflated.

In code, count the new letter and update the top count. If the window needs more than k changes, drop the left letter. Keep the best length.

Let's run the second example. A, A: the top count is two. B: one change, fine. A: top count three, four letters, best four. B: five letters need two changes, so slide. A, B, A, B really needs two, but size four already worked. B, then A: slide, slide. Best stays four.

Each letter enters and leaves the window at most once: order n time. At most twenty six counts: order one space.

Count, grow, slide when you must. That's Longest Repeating Character Replacement.