자리 바꾸기
시간 제한2초메모리 제한512 MB
A, B, C로 이루어진 원형 문자열이 주어질 때, 각 문자가 하나의 연속 구간을 이루도록 만드는 최소 교환 횟수를 구한다.
문제
원형 탁자에 N명이 둘러앉아 긴 협상을 진행한다. 각 사람은 A, B, C 세 그룹 중 하나에 속한다. 어떤 그룹의 구성원이 모두 연속한 좌석에 붙어 앉아 있으면 그 그룹은 행복하다고 한다. 자리 바꾸기 연산을 여러 번 수행해 모든 그룹을 행복하게 만들려고 한다. 자리 바꾸기 연산에서는 두 사람이 서로 자리를 바꾼다. 모든 그룹을 행복하게 만드는 데 필요한 최소 자리 바꾸기 횟수는 얼마인가?
입력
입력은 A, B, C 중 하나인 문자 N개(1 ≤ N ≤ 1 000 000)로 이루어진 한 줄이다. i번째 문자는 탁자의 i번째 좌석에 처음 앉아 있는 사람의 그룹을 나타내며, 좌석은 시계 방향으로 번호가 매겨진다.
출력
가능한 최소 자리 바꾸기 횟수를 정수 하나로 출력한다.