Problem Description

The demand for talent in the IT industry keeps rising. Industry giants Baidu, Alibaba, and Tencent (abbreviated as BAT) hold a recruitment event on a beach.

The recruiting booths are arranged in a single line. Since seats are taken freely, the seats of the three companies are randomly mixed together, for example:

ABABTATT, which makes applicants feel uncomfortable.

So, the management requires the recruiters to swap positions when necessary, so that the seats of each group are all next to each other. That is, the final arrangement should look like:

BBAAATTT, of course, it could also be:

AAABBTTT, etc.

Now, suppose that each time you can only swap $2$ seats, and you are given the current seat arrangement.

Your task is to compute: to make the recruiting seats of each group all adjacent, what is the minimum number of swaps needed.

Input Format

The input is one line with $n$ characters (only the letters B, A, or T), representing the current seat arrangement.

Output Format

Output one integer, representing the minimum number of swaps.

TABTABBTTTT

3

TTAAABB

0

Hint

The length $n$ of the input string is at most $10^5$.

Time limit: 1 second, 256M. Lanqiao Cup 2018, 9th National Finals.

Translated by ChatGPT 5