같은 글자

면접 대비

시간 제한2초메모리 제한1024 MB

요약

소문자로 된 문자열 S와 정수 m이 주어질 때, 최대 m개의 문자를 지워 만들 수 있는 같은 문자의 가장 긴 연속 구간의 길이를 구합니다.

문제

컴퓨터 과학자들은 같은 글자가 연속으로 나타나는 구간에 늘 관심을 갖는다. 그래서 문자열에서 같은 글자가 가장 길게 이어지는 구간을 찾는다.

소문자로만 이루어진 문자열 $S$ 와 정수 $m$ 이 주어진다. $S$ 에서 최대 $m$ 개의 글자를 지웠을 때, 같은 글자가 연속으로 나타나는 최대 개수를 구하라. $m$ 개를 정확히 지울 필요는 없다.

첫째 줄에 문자열 $S$ 가 주어진다. $S$ 는 소문자로만 이루어지며, 길이는 $1$ 이상 $2 \times 10^5$ 이하이다.

둘째 줄에 정수 $m$ ( $0 \le m \le |S|$ )이 주어진다. 지울 수 있는 글자의 최대 개수이다.

문자열에서 최대 $m$ 개의 글자를 지웠을 때 얻을 수 있는, 같은 글자가 연속으로 나타나는 최대 개수를 출력한다.

첫 번째 예제에서는 10번째와 11번째 글자를 지우면 된다.

두 번째 예제에서는 3, 4, 6, 10, 11번째 글자를 지우면 된다.

세 번째 예제에서는 a가 두 개 연속된 형태나 y가 두 개 연속된 형태를 만들 수 있으며, 길이는 각각 2이다.