A museum's floor mosaic is laid out as a single row of n tiles, each tile currently either cracked ('C') or polished ('P'). Curators want to find a run of k consecutive tiles that are all polished, so they can rope it off as a display strip, and they want to spend as little restoration effort as possible getting there.
Restoring one cracked tile to polished counts as one unit of effort; polished tiles never need to be touched. Determine the minimum number of tiles that must be repolished so that some window of exactly k consecutive tiles is entirely polished.
Line 1: two integers n and k. Line 2: a string of length n consisting only of the characters 'C' and 'P', describing the current state of each tile from left to right.
Print a single integer: the minimum number of tiles that must be repolished.
Example 1
Input
8 3 CPPCPCCP
Expected
1
Explanation
The tiles are C P P C P C C P (indices 0-7). Checking every window of length 3: [0,2]=CPP has 1 cracked, [1,3]=PPC has 1, [2,4]=PCP has 1, [3,5]=CPC has 2, [4,6]=PCC has 2, [5,7]=CCP has 2. The smallest cracked count among these windows is 1 (for example the window CPP at indices 0-2, needing only the tile at index 0 repolished), so the answer is 1.
Example 2
Input
6 3 PPPCPP
Expected
0
Explanation
The first three tiles are P P P -- already all polished, with 0 cracked tiles in that window -- so no repolishing is needed at all. The answer is 0.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →