There are \(N\) 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?

\((1\le N\le 1\:000\:000)\)
\(N\le 5\:000\)

The input consists of a single line containing \(N\) \((1\le N\le 1\:000\:000)\) characters, where each character is
A, B, or
C. The \(i\)-th character denotes the group of the
person initially sitting at the \(i\)-th seat at the table, where seats are
numbered in clockwise order.

For 4 of the 15 available marks, the input has no
C characters and \(N\le 5\:000\).

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

For an additional 4 of the 15 available marks, \(N\le 5\:000\).

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

생성자가 기록되지 않았습니다.

출처 CCC 2020 Senior