Loading...
Loading...
Loading...
A rangoli border is a row of coloured tiles. Each colour is written as a capital letter, so the border is a string such as ABAB.
You may repaint at most k tiles, each to any colour. Find the length of the longest continuous run of tiles that all have the same colour after repainting.
Example 1
Input
ABAB 2
Output
4
Repaint both B tiles to A: the whole border is one colour.
Example 2
Input
AABABBA 1
Output
4
Repaint the A at position 4 to get BBBB, a run of 4.
Try the problem first. Open one hint at a time.
A piece of the border can become one colour if (its length) − (count of its most common colour) ≤ k.
So you want the longest piece that passes this test. A piece that grows on the right and shrinks on the left can find it.
Keep 26 counts for the letters inside the piece. After adding a letter on the right, shrink from the left while the piece needs more than k repaints.
Record the length after each step. Finding the most common count by scanning 26 counters is fast enough.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor