Longest Same-Letter Run With k Changes
You get a string s made of uppercase English letters (A to Z) and an integer k.
You may choose at most k positions in s and change the letter at each of them to any uppercase letter. You may also change nothing.
After the changes, look at every substring of s in which all letters are the same. A substring is a block of letters that sit next to each other in s. Return the length of the longest such substring you can make.
Note
- You do not have to use all
kchanges. - The answer is never larger than
s.length.
Hint: a window of s can become one repeated letter when the number of letters in it that are not its most common letter is at most k. Move the right end of the window forward one step at a time, and move the left end forward when this rule breaks.
Examples
Example 1
- Input:
- "XYYXYYYX", 1
- Output:
- 6
Change the X at index 3 to Y. Then indexes 1 to 6 are "YYYYYY", which has length 6. To get 7 or 8 letters you would need to change at least 2 letters.
Example 2
- Input:
- "MMMM", 2
- Output:
- 4
The string is already one repeated letter. No change is needed, and a run can not be longer than the string.
Example 3
- Input:
- "PQRS", 0
- Output:
- 1
No changes are allowed and all four letters are different, so the longest run has length 1.
Constraints
1 <= s.length <= 40shas only uppercase English letters.0 <= k <= s.length
Run checks your code against the 3 examples. Submit checks it against all 153 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.