158. Repaint to Repeat
A fence is made of boards, and board i is painted with the lowercase letter s[i]. A painter has enough paint to change the colour of at most k boards, and each repainted board can be given any lowercase letter.
After repainting, the painter wants a stretch of consecutive boards that all show the same letter, as long as possible. Return the length of the longest such stretch that can be produced using at most k repaints. Boards outside the chosen stretch do not matter, and you may use fewer than k repaints, or none at all.
Example 1
- Input:
- s = "aabbbab", k = 1
- Output:
- 5
- Explanation:
Repaint the single a inside bbbab to get bbbbb, a stretch of 5 equal boards. No window of 6 needs only one repaint, so the answer is 5.
Example 2
- Input:
- s = "abc", k = 0
- Output:
- 1
- Explanation:
No repaints are allowed and no two neighbouring boards match, so the best stretch is a single board, length 1.
Example 3
- Input:
- s = "xyxyx", k = 2
- Output:
- 5
- Explanation:
The whole string has three x and two y, so repainting the two y turns it into xxxxx, and the answer is 5.
Constraints
1 ≤ s.length ≤ 105
s consists of lowercase English letters.
0 ≤ k ≤ s.length
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)