JJOOII

면접 대비

시간 제한1초메모리 제한128 MB

요약

주어진 문자열에서 J k개, O k개, I k개가 연속으로 나타나는 가장 큰 k를 구한다.

난이도: 보통10점 중 5점
유형: 문자열, 누적 합, 이분 탐색
정답자: 아직 제출이 없습니다

문제

J, O, I 세 종류의 문자로만 이루어진 문자열을 다룬다.

문자열 $t$ 가 문자열 $s$ 의 부분 문자열이라는 것은, $t$ 의 앞과 뒤에 각각 $0$ 개 이상의 문자를 덧붙여서 $s$ 를 만들 수 있다는 뜻이다. 즉 $t$ 는 $s$ 안에 연속으로 나타나야 한다. 예를 들어 JJOOII는 OJJOOIIOJOI의 부분 문자열이지만, JOI는 JOOI의 부분 문자열이 아니다.

$0$ 이상의 정수 $k$ 에 대하여, 레벨 $k$ 의 JOI 열이란 문자 J를 $k$ 개, 문자 O를 $k$ 개, 문자 I를 $k$ 개 이 순서대로 이어 붙인 문자열이다. 예를 들어 JJOOII는 레벨 $2$ 의 JOI 열이다.

J, O, I 세 종류의 문자로 이루어진 길이 $N$ 의 문자열 $S$ 가 주어진다. 레벨 $k$ 의 JOI 열이 $S$ 의 부분 문자열이 되는 최대의 $k$ 를 구하여라.

입력

첫째 줄에 J, O, I 세 종류의 문자로 이루어진 문자열 $S$ 가 주어진다.

출력

레벨 $k$ 의 JOI 열이 $S$ 의 부분 문자열이 되는 최대의 $k$ 를 한 줄에 정수로 출력하여라. (레벨 $1$ 이상의 JOI 열이 하나도 부분 문자열이 아니면 0을 출력한다.)

제한

$1 \le N \le 1\,000\,000$ (여기서 $N$ 은 문자열 $S$ 의 길이이다.)

예제4

예제 1
입력
```
OJJOOIIOJOI
```
예상 출력
```
2
```
예제 2
입력
```
IJJIIJJJ
```
예상 출력
```
0
```
예제 3
입력
```
JOIJOIJOIJOIJOI
```
예상 출력
```
1
```
예제 4
입력
```
OOJJJJJJJOOOOIIIII
```
예상 출력
```
4
```