Description

There are $N$ people sitting around a round table.

There are three groups, and each person belongs to one group.

Now you want people from the same group to sit together.

Each time, you may swap the seats of two people. Output the minimum number of swaps.

Input Format

A single line containing a string $s$ of length $N$, representing the groups of all people in clockwise order.

If $s_i$ is A, then the $i$-th person belongs to the first group, and so on.

Output Format

A single line containing one integer, the minimum number of swaps.

BABCBCACCA

2

Hint

Sample Explanation

$\texttt{BABCBCACCA}\to\texttt{AABCBCBCCA}\to\texttt{AABBBCCCCA}$.

Subtasks

This problem uses bundled testdata, and the Subtask scores have been slightly adjusted.

• Subtask 1 ($26$ points): $s_i\in\{$A$,$B$\}$ and $N\le 5\times 10^3$.
• Subtask 2 ($27$ points): $s_i\in\{$A$,$B$\}$.
• Subtask 3 ($27$ points): $N\le 5\times 10^3$.
• Subtask 4 ($20$ points): No special constraints.

For $100\%$ of the testdata, it is guaranteed that $s_i\in\{$A$,$B$,$C$\}$ and $1\le N\le 10^6$.

Notes

This problem is translated from Canadian Computing Competition 2020 Senior T4 Swapping Seats.

Translated by ChatGPT 5