Buma의 공

시간 제한3초메모리 제한512 MB

요약

색깔 공이 일렬로 놓여 있을 때, 새 공의 색과 넣을 위치를 골라 연쇄 반응으로 모든 공을 없애는 경우의 수를 센다.

난이도: 보통10점 중 6점
유형: 문자열, 구현, 시뮬레이션, 투 포인터
정답자: 아직 제출이 없습니다

문제

Balph는 Buma라는 게임을 배우고 있다. 이 게임에서 그는 색깔이 있는 공 한 줄을 받는다. 그는 새 공 하나의 색을 정하고, 그 공을 넣을 위치(두 공 사이, 모든 공의 왼쪽, 또는 모든 공의 오른쪽)를 정해야 한다.

공을 넣으면 다음 과정이 반복된다. 이전 동작의 결과로 같은 색 공의 어떤 구간이 길어졌고 그 길이가 $3$ 이상이 되면, 그 구간의 공이 모두 제거된다.

예를 들어 공의 줄 'AAABBBWWBB'를 보자. Balph가 색 'W'인 공을 골라 여섯 번째 공 뒤, 즉 두 'W'의 왼쪽에 넣는다고 하자. 이 공을 넣으면 색 'W'의 공들이 제거된다. 이 구간이 길어져 길이가 $3$ 이 되었기 때문이며, 줄은 'AAABBBBB'가 된다. 이제 색 'B'의 공들이 제거된다. 색 'B'의 공 구간이 길어져 길이가 $5$ 가 되었기 때문이다. 따라서 줄은 'AAA'가 된다. 하지만 이제는 길어진 구간이 없으므로 어떤 공도 제거되지 않는다.

Balph를 도와 모든 공을 제거하게 되는, 새 공의 색과 넣을 위치를 고르는 방법의 수를 세어라.

입력

첫째 줄에 길이가 $3 \cdot 10^5$ 이하인, 영문 대문자로 이루어진 비어 있지 않은 문자열이 주어진다. 각 문자는 해당 색의 공을 나타낸다.

출력

모든 공을 제거하도록 새 공의 색과 위치를 고르는 방법의 수를 출력한다.

예제5

예제 1
입력
```
BBWWBB
```
예상 출력
```
3
```
예제 2
입력
```
BWWB
```
예상 출력
```
0
```
예제 3
입력
```
BBWBB
```
예상 출력
```
0
```
예제 4
입력
```
OOOWWW
```
예상 출력
```
0
```
예제 5
입력
```
WWWOOOOOOWWW
```
예상 출력
```
7
```