You get a string s of capital letters and a budget k. You may overwrite up to k characters of s, each with any capital letter you like.
After your changes, look for the longest run of consecutive characters that are all the same letter. Return the longest such run you can make.
Overwrite the first B with A: AAAAB holds a run of four As. Overwriting both Bs would make five, but that needs two changes.
With no changes allowed, the answer is the longest run already there: BBB.
Turn the Y and the Z of XYZX into X to get XXXXY. All five letters can't be made equal with two changes, because no letter appears more than twice.
Constraints
1 <= s.length <= 10⁵s is made of uppercase English letters only.0 <= k <= s.lengthA run can be made all one letter if the number of characters that aren't its most common letter is at most k. So look at windows of s, not at which letters to change.
Take any stretch of s. The cheapest way to make it all one letter is to keep its most common letter and overwrite everything else. So a window of length len, whose most common letter appears top times, costs exactly len - top changes. It can be made uniform if and only if
Time O(n)Space O(1)
The full walkthrough and code are part of Premium
4