Longest Repeating Character Replacement
The problem
For a string of uppercase English letters and a budget k, find the longest substring that can become one repeated letter after changing at most k positions.
Example
s = "AABBA", k = 1 → 3
Need a hint?
Required replacements equal window length minus its largest letter count.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Expand a window and count letters. While window length minus the current maximum of the 26 counts exceeds k, remove the leftmost character and advance left. Track the largest valid window. Recomputing the maximum keeps the invariant explicit and costs only a fixed factor.
Complexity
O(26n), hence O(n), time and O(26) space.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.