ABC String

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

요약

A, B, C의 개수가 같은 문자열을, 각각 한 글자씩 들어 있는 길이 3 블록으로 나뉘는 부분수열들로 최소 개수만큼 분할하는 문제입니다.

난이도: 어려움10점 중 8점
유형: 그리디, 동적 계획법, 문자열, 구현
정답자: 아직 제출이 없습니다

문제

You're given a string consisting of the characters A, B, and C. The string contains the same count of A, B, and C characters.

A string is beautiful if

Its length is divisible by $3$ .
The string can be split evenly into contiguous substrings of size $3$ , where each substring has one A, one B, and one C, in any order.

For example: ABCCBA is a beautiful string, but ABCAB and CCBAAB are not beautiful.

Given a string, you want to partition it into subsequences (not necessarily contiguous) such that each subsequence is a beautiful string.

For example, for the string ABACBCAACCBB, we can do the following:

AB   CA C B
  ACB  A C B

This partitions the string into two subsequences ABCACB and ACBACB, both of which are beautiful strings.

For the given string, find the minimum number of subsequences you can partition it into such that each subsequence is beautiful. It can be proven that there is always at least one such partition for all possible inputs that satisfy the input constraints.

입력

The first line of input contains a string $s$ ( $3 \le |s| \le 3 \cdot 10^5$ ). $|s|$ is divisible by $3$ . $s$ contains an equal number of characters A, B, and C.

출력

Output a single integer, which is the minimum subsequences that $s$ can be partitioned into so each subsequence is a beautiful string.

예제1

예제 1
입력
```
ABACBCAACCBB
```
예상 출력
```
2
```