Best run after k changes
MediumStuck?
Show a hintHide the hint
A window works when its size minus the count of its most common letter is at most k. Slide the window rather than shrinking it.
The ideas behind this problem
Next in this lesson
Two sum in a sorted listYou may change up to k letters of a word to any other letters. Find the length of the longest run of a single repeated letter you can end up with.
Worked example#
For AABABBA with k = 1, a window is usable when the letters inside it that are not the most common one number at most k, because those are the ones you would change:
| window | most common | others | changes needed | usable with k = 1 |
|---|---|---|---|---|
| AAB | A, twice | 1 | 1 | yes, length 3 |
| AABA | A, three times | 1 | 1 | yes, length 4 |
| AABAB | A, three times | 2 | 2 | no, shrink |
| ABAB | A and B, twice each | 2 | 2 | no, shrink |
| BAB | B, twice | 1 | 1 | yes, length 3 |
| BABB | B, three times | 1 | 1 | yes, length 4 |
| BABBA | B, three times | 2 | 2 | no, shrink |
The best is 4.
The trick that keeps this to a single pass: track the count of each letter in the window and the highest count ever seen. The window only needs to grow when a better answer is possible, and a better answer needs a higher count than the best so far, so the highest-count figure never has to be recomputed downward. The window then only ever grows or slides, never shrinks past what it has already proved.
Constraints#
1 <= length <= 100000- Uppercase letters only
0 <= k <= length
Input
s is one word of uppercase letters, then k is one integer.
Output
The longest run of one repeated letter that is reachable.
Examples
Input
ABAB 2
Output
4
Change both Bs to As and the whole word is one run.
Input
AABABBA 1
Output
4
Changing the single B in AABA gives AAAA, which is four long.
Input
AAAA 0
Output
4
Already one run, and no changes are needed.
Something wrong with this problem? Report an issue
Ready to try it
Write your solution in C, C++, Java or Python and see every test case come back with the time and memory it took.
Free, and it stays free. No card.