Uniform Fence After Repainting

A fence is a string fence of uppercase letters, each letter being a paint colour. You have enough paint to recolour at most k boards to any colour you like. Return the length of the longest stretch of consecutive boards that can be made a single colour.

Examples

Input:  fence = "ABAB", k = 2
Output: 4
Explanation: repaint both B boards (or both A boards).

Input:  fence = "AABABBA", k = 1
Output: 4
Explanation: repaint the middle B to get "AAAA" from index 0 to 3.

Constraints

• 1 <= len(fence) <= 10**5
• fence consists of uppercase English letters, 0 <= k <= len(fence)
• Target complexity: O(n) time; checking every substring is too slow for the largest tests.

Goals

• Express the window constraint in terms of its most frequent character
• Use a window that never shrinks below the best length found