mediumSliding windowHash maps and sets target 25 min
Longest run after a few changes
A string s holds uppercase letters. You may change at most k of its letters, each into any uppercase letter. You do not have to use all k changes.
Return the length of the longest block of consecutive positions that can be made all the same letter. The changes are imagined: return the length and leave s as it is.
Example 1
Input
s = "ABBA", k = 1Output3Change the first A to B: "BBBA" starts with three B's. A block of four would need two changes.
Example 2
Input
s = "CCDCCD", k = 1Output5Change the first D to C: "CCCCCD" starts with five C's. All six letters would need both D's changed.
Example 3
Input
s = "XYZ", k = 0Output1With no changes allowed, the longest block of one letter has length 1.
Constraints
1 ≤ len(s) ≤ 105
s holds only uppercase letters A to Z.
0 ≤ k ≤ len(s)
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.
Run examples checks the examples. Submit runs every test, including edge cases and, when the problem has one, a speed check on a large input.