题目描述

有 $N$ 个人坐在一张圆桌旁。

共有三个派别，每一个人属于一个派别。

现在，您想使属于同一派别的人坐到一起。

您可以每次将两个人交换位置，输出最小的交换次数。

输入格式

仅一行一个长度为 $N$ 的字符串 $s$，为顺时针所有人的派别。

如果 $s_i$ 为 A，则说明第 $i$ 个人为第一个派别的，以此类推。

输出格式

仅一行一个整数，表示最小的交换次数。

BABCBCACCA

2

提示

样例解释

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

子任务

本题采用捆绑测试，且本题的 Subtask 分数有微调。

• Subtask 1（$26$ 分）：$s_i\in\{$A$,$B$\}$ 且 $N\le 5\times 10^3$。
• Subtask 2（$27$ 分）：$s_i\in\{$A$,$B$\}$。
• Subtask 3（$27$ 分）：$N\le 5\times 10^3$。
• Subtask 4（$20$ 分）：无特殊限制。

对于 $100\%$ 的数据，保证 $s_i\in\{$A$,$B$,$C$\}$，$1\le N\le 10^6$。

说明

本题译自 Canadian Computing Competition 2020 Senior T4 Swapping Seats。