Uniform Run After K Edits
MediumSliding Window
Problem
A string s of uppercase letters describes the colours of tiles in a row. You may repaint at most `k` tiles, each to any colour.
Return the length of the longest block of consecutive tiles that can be made a single colour.
Example 1
- Input:
- s = "BAAAB", k = 1
- Output:
- 4
Repaint either B to A: "AAAAB" or "BAAAA" has a run of four.
Example 2
- Input:
- s = "ABCD", k = 0
- Output:
- 1
Constraints
- 1 ≤ s.length ≤ 10^5
- s contains only uppercase English letters.
- 0 ≤ k ≤ s.length
Hint
Show the first hint
For a fixed window, how many repaints does it need to become one colour?
Walkthrough
How to approach it
01Clarify before coding
- Must every repainted tile become the same colour? Only within the block you are measuring; the best plan repaints everything else in the block to its majority colour.
- Can k be 0? Yes; then the answer is the longest existing run.
- Only uppercase letters? Yes, 26 colours.
02Brute force
For each start, extend to the right while tracking letter counts; the window is feasible if its length minus its top count is ≤ k.
Cost: O(n²) time (each start scans to the end), too slow for 10^5.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.