ABC String

Time limit1sMemory limit2048 MB

Summary

Partition a string with equal counts of A, B, and C into the fewest subsequences, where each subsequence splits into consecutive triples that each contain one of every letter.

Level: Hard8 of 10
Topics: String, Greedy, Dynamic programming
Solved: No attempts yet

Problem

You are given a string $s$ consisting of the characters A, B, and C. The string contains the same number of A, B, and C characters.

A string is beautiful if:

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

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

You want to partition the given string into subsequences (not necessarily contiguous) so that each subsequence is beautiful. For example, the string ABACBCAACCBB can be partitioned as follows:

AB   CA C B
  ACB  A C B

This gives two subsequences, ABCACB and ACBACB, and both are beautiful. The input always admits at least one such partition.

Find the minimum number of subsequences needed to partition the string so that each one is beautiful.

Input

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

Output

Print a single integer, the minimum number of beautiful subsequences that $s$ can be partitioned into.

Examples1

Example 1
Input
```
ABACBCAACCBB
```
Expected output
```
2
```