Identical Letters
시간 제한2초메모리 제한1024 MB
소문자 문자열과 예산 m이 주어질 때, 최대 m개의 문자를 지워 같은 문자가 연속한 구간의 최대 길이를 구한다.
문제
Streak of identical letters always fascinates computer scientists and, as such, the scientists always look for such consecutive sequence of identical letters.
Given a string of lowercase letters and an integer m, determine the maximum number of consecutive identical letters in the string if you can remove up to m letters from the string. Note that you do not have to remove exactly m letters.
입력
The first input line provides the string (1 ≤ string length ≤ 2×105); it starts in column 1 and contains only lowercase letters. The second input line contains an integer, m (0 ≤ m ≤ string length), indicating the maximum number of letters you can remove from the string.
출력
Print the maximum number of consecutive identical letters in the string if you can remove up to m letters from the string.
힌트
For the first Sample Input, we can remove the two letters at positions 10 and 11.
For the second Sample Input, we can remove the letters at positions 3, 4, 6, 10 and 11.
For the third Sample Input, we can create ”…aa…” or ”…yy…”, each of length 2.