AlgoLensArena
ContestlərProblemlərOtaqlar
Vizualizator
← Məsələlər

BAPC18-035.Game Night

Medium · 1 s · 256 MB

  • icpc
  • bapc
  • 2018

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 how well he knows them: the Acquaintances on team AAA, the Buddies on team BBB, and the Colleagues on team CCC.

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?

Giriş formatı

• The first line of the input contains the integer nnn, where 1≤n≤1051 \leq n \leq 10^51≤n≤105 is the number of players (as well as seats).

• The second line contains a string of length nnn, consisting only of the characters in ABC. This indicates the teams of the people sitting around the table in order.

Çıxış formatı

Print a single integer: the minimal number of people you have to ask to move seats to make sure the teams sit together.

Qeyd

Source: Benelux Algorithm Programming Contest 2018 · Author: <author name> · License: CC BY-SA 4.0 · Original: https://bapc.eu · Statement adapted for AlgoLens and shared under the same license.

Nümunələr

Giriş #1

5
ABABC

Çıxış #1

2

Giriş #2

12
ABCABCABCABC

Çıxış #2

6

Giriş #3

4
ACBA

Çıxış #3

0

Giriş #4

6
BABABA

Çıxış #4

2

Giriş #5

9
ABABCBCAC

Çıxış #5

3