31506번 - ABC String 다국어

문제

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.

제한

힌트