Longest single-colour run after repainting k tiles

A window is fixable if its length minus the count of its most common colour is at most k. Grow the window, update counts and the best count seen, and shrink by one when the window is not fixable. The best count never needs to decrease for the answer to stay right, so each step is O(1): O(n) total, with O(c) space for the counts of c colours.

Not lowering top when the window shrinks is safe: the answer only grows when a window with a higher top count appears.

Recomputing max(counts) each step is O(26) and also fine; it is easier to explain.

The window never shrinks by more than one per step, so its size is the best answer so far.

def longest_after_repaints(row: str, k: int) -> int:
    counts: dict[str, int] = {}
    left = top = best = 0
    for right, colour in enumerate(row):
        counts[colour] = counts.get(colour, 0) + 1
        top = max(top, counts[colour])
        if right - left + 1 - top > k:
            counts[row[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

Common mistakes

• Trying every colour as the target separately and doing it badly in O(26·n²).
• Shrinking in a while loop and recomputing the top count every time, then getting confused about correctness.

If you use the 'never decrease top' trick, explain why it is safe; otherwise recompute and say it is O(26n).

Follow-up questions

Think of your answer first, then open the hint.

1. What if repaints have different costs per tile?

   Show hint

   Then it is a budget window with costs instead of counts.

2. How do you return which colour wins?

   Show hint

   Track the colour that set top when best improves.