Longest Repeating Character Replacement

You may change up to k characters of an uppercase string to any letter. Return the length of the longest substring of one repeated letter you can make.

A way to picture it

You're repainting a fence with k cans of paint. Look at any stretch: keep the most common colour, repaint everything else. The stretch is doable if the planks that need repainting fit in your k cans.

How to approach it

A window is fine when (length − count of its most common letter) ≤ k. Grow the right edge; if the window breaks, slide the left edge along by one.

Example

Input: {"s":"ABAB","k":2}. Output: 4.

Complexity: O(n) time and O(26) space. Both pointers only move forward; the counts cover 26 letters.

This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.