You are given a string s of uppercase English letters and an integer k. You may change any
character of s into any other uppercase letter, at most k times in total.
Return the length of the longest substring that holds a single repeated letter after your changes.
Example 1
- Input
- s = "ABBCB", k = 1
- Output
- 4
C to B, and BBCB becomes BBBB.Example 2
- Input
- s = "AABCAAB", k = 2
- Output
- 6
AABCAA has four As; changing its B and C gives six As in a row.Example 3
- Input
- s = "XYZ", k = 0
- Output
- 1
Constraints
sholds 1 to 10⁵ letters, each fromAtoZ.- 0 ≤
k≤ the length ofs
Show the pattern
Sliding window
You want the longest contiguous stretch that can be made into one repeated letter. A window works while its length minus its most common letter's count is at most k, so grow it on the right and shrink it on the left when it stops working.
See sliding window in a visualiserShow the approach
Slide a window over s, counting the letters inside it. A window can be made into one repeated
letter with length − (count of its most common letter) changes. Move right one step at a
time, adding its letter to the counts. While the window would need more than k changes, take
its leftmost letter out of the counts and move left on. Every window you keep is usable, so the
answer is the longest one seen.
Finding the most common letter means looking at no more than 26 counts, so the pass is O(26 · n). (A known refinement keeps the highest count ever reached instead of recomputing it, which gives the same answer in O(n).)
Time: O(26 · n), which is O(n) · Space: O(1): at most 26 counts