At most k replacements in the window
Updated
Longest window that can become one repeating character by changing at most k other cells. Valid iff (R-L+1) - maxFreq ≤ k.
What to focus on
Expand R, update maxFreq, then shrink while length - maxFreq > k. maxFreq is the best count of a single character in the current window, not a global.
Worked examples
k=1 abca
s = "abca", k=1- [0,1] "ab" 2-1=1 ok len 2
- [0,2] "abc" 3-1=2>1 drop a → "bc" ok
- [1,3] "bca" 3-1=2>1 drop b → "ca" ok
Result: best length 2
k=1 aaba
s = "aaba", k=1- "aab" maxFreq a=2, 3-2=1 ok
- "aaba" maxFreq a=3, 4-3=1 ok
Result: best length 4
k=0 run
s = "aaab", k=0- change none: length must equal maxFreq
- "aaa" 3-3=0
- add b → 4-3=1>0 shrink
Result: best length 3
Try it
Write longestSameWithK(s, k). s is a string of letters. k is the replacement budget. L is the left index. R is the right index. The window includes s[L..R]. Valid means (R-L+1) - maxFreq ≤ k. Return the best length. Trace "abca" k=1, "aaba" k=1, "aaab" k=0.
s is a nonempty string of letters. k ≥ 0.