문자열 교환

면접 대비

시간 제한2초메모리 제한128 MB

요약

a와 b로 이루어진 원형 문자열에서 모든 a를 한 블록으로 모으는 데 필요한 최소 스왑 횟수를 구합니다.

문제

a와 b로만 이루어진 문자열이 주어진다. 이 문자열에서 문자를 서로 교환하여 모든 a가 연속한 구간에 모이도록 하려고 한다. 필요한 교환 횟수의 최솟값을 구하라.

문자열은 원형으로 보므로, 첫 문자와 마지막 문자도 서로 이웃한다.

예를 들어 aabbaaabaaba는 두 번의 교환으로 모든 a를 연속하게 만들 수 있다.

첫째 줄에 a와 b로만 이루어진 문자열이 주어진다. 문자열의 길이는 최대 1,000이다.

모든 a를 연속하게 만들기 위해 필요한 교환 횟수의 최솟값을 출력한다.