##### Canadian Computing Competition: 2020 Stage 1, Senior #4

There are people sitting at a circular table for a long session of negotiations. Each person belongs to one of the three groups: `A`

, `B`

, or `C`

. A group is *happy* if all of its members are sitting contiguously in a block of consecutive seats. You would like to make all groups happy by some sequence of *swap* operations. In each swap operation, two people exchange seats with each other. What is the minimum number of swaps required to make all groups happy?

#### Input Specification

The input consists of a single line containing characters, where each character is `A`

, `B`

, or `C`

. The -th character denotes the group of the person initially sitting at the -th seat at the table, where seats are numbered in clockwise order.

For of the available marks, the input has no characters and .

For an additional of the available marks, the input has no characters.

For an additional of the available marks, .

#### Output Specification

Output a single integer, the minimum possible number of swaps.

#### Sample Input

`BABCBCACCA`

#### Output for Sample Input

`2`

#### Explanation of Output for Sample Input

In one possible sequence, the first swap results in the seating layout `AABCBCBCCA`

. After the second swap, the layout is `AABBBCCCCA`

.

## Comments

For the sample input, why is

`AABBBCCCCA`

the correct final sort? Why doesn't it need to be`AAABBBCCCC`

for the A group to be happy?They are arranged in a ring, not in a row.

The table is circular.

I don't understand how "AABCBCBCCA" can become "AABBBCCCCA" in just one swap. Can someone explain?

Swap these 2 characters.

Oh I see, thank you.

Can we assume there will always be >2 of each type? (in the case that one exists)

It's not in the statement, so probably not. I don't know why they would exclude cases like .