그렇게 거칠진 않게

면접 대비

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

요약

소문자로 된 문자열과 정수 c가 주어질 때, 앞의 a와 뒤의 b로 이루어진 쌍이 c 이하인 가장 긴 부분 문자열의 길이를 구합니다.

난이도: 보통10점 중 5점
유형: 슬라이딩 윈도우, 문자열
정답자: 아직 제출이 없습니다

문제

T'Challa는 마지막 싸움에서 Killmonger와 맞붙게 되었다. 영화 내내 지친 두 사람은 더 차분한 지적 경쟁으로 승부를 가리기로 했다.

먼저 Killmonger가 소문자 라틴 문자 $n$ 개로 이루어진 문자열 $s_1 s_2 \ldots s_n$ 을 정한다.

문자열 $t_1 t_2 \ldots t_k$ 의 거칠기는 $1 \le i < j \le k$ 를 만족하는 쌍 $(i, j)$ 중 $t_i =$ a이고 $t_j =$ b인 쌍의 개수이다. 즉 두 글자만 남기고 나머지를 지워서 a, b 순서의 두 글자가 남는 방법의 수이다.

문자열이 정해지면 T'Challa는 공백이 아닌 부분 문자열 $s_l s_{l+1} \ldots s_r$ 을 하나 고른다. 거칠기가 $c$ 를 넘으면 기술적 패배로 처리된다. 거칠기가 $c$ 이하인 부분 문자열 중 가장 긴 것을 고르면 T'Challa가 이긴다. 최대 길이의 부분 문자열이 여럿이면 그중 어느 것을 골라도 된다.

입력

첫 줄에 정수 $n$ 과 $c$ 가 주어진다. $n$ 은 문자열의 길이이고, $c$ 는 고를 수 있는 부분 문자열의 최대 거칠기이다 ( $1 \le n \le 10^6$ , $0 \le c \le 10^{18}$ ).

둘째 줄에 Killmonger가 정한 문자열 $s$ 가 주어진다. $s$ 는 $n$ 개의 소문자 라틴 문자로 이루어진다.

출력

거칠기가 $c$ 이하인 부분 문자열의 최대 길이를 한 줄에 출력한다.

예제2

예제 1
입력
```
3 1
aab
```
예상 출력
```
2
```
예제 2
입력
```
6 2
aabcbb
```
예상 출력
```
4
```