Problem G
Game Night
It is finally Bobby’s birthday, and all of his Acquaintances, Buddies and Colleagues have gathered for a board game night. They are going to play a board game which is played in up to three big teams. Bobby decided to split his guests into groups based on how well he knows them: the Acquaintances on team $A$, the Buddies on team $B$, and the Colleagues on team $C$.
While Bobby was busy explaining the rules to everyone, all his guests already took seats around his large, circular living room table. However, for the game it is crucial that all people sitting on a team are sitting next to each other. Otherwise, members of other teams could easily eavesdrop on their planning, ruining the game. So some people may need to change seats to avoid this from happening.
Bobby wants to start playing the game as soon as possible, so he wants people to switch seats as efficiently as possible. Given the current arrangement around the circular table, can you figure out the minimal number of people that must switch seats so that the teams are lined up correctly?
Input
-
The first line of the input contains the integer $n$, where $1 \leq n \leq 10^5$ is the number of players (as well as seats).
-
The second line contains a string of length $n$, consisting only of the characters in ABC. This indicates the teams of the people sitting around the table in order.
Output
Print a single integer: the minimal number of people you have to ask to move seats to make sure the teams sit together.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 ABABC |
2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
12 ABCABCABCABC |
6 |
| Sample Input 3 | Sample Output 3 |
|---|---|
4 ACBA |
0 |
| Sample Input 4 | Sample Output 4 |
|---|---|
6 BABABA |
2 |
| Sample Input 5 | Sample Output 5 |
|---|---|
9 ABABCBCAC |
3 |
