P6709 [CCC 2020] Swapping Seats

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.

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.

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

#### 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](https://cemc.uwaterloo.ca/resources/past-contests?contest_category=29) [2020 Senior](https://cemc.uwaterloo.ca/sites/default/files/documents/2020/seniorEF.pdf) T4 Swapping Seats. Translated by ChatGPT 5