바나나나빠나나

'유사 바나나'는 다음 규칙으로 정의된다.

• $BANANA$는 유사 바나나이다.
• 유사 바나나 $X$에 대하여 $B$를 앞에 붙인 $BX$도 유사 바나나이다.
• 유사 바나나 $X$에 대하여 $NA$를 뒤에 붙인 $XNA$도 유사 바나나이다.

따라서 모든 유사 바나나는 $B^{a}ANANA(NA)^{t}$ 꼴이며, 여기서 $a$는 1 이상, $t$는 0 이상의 정수이다. 길이는 $a + 5 + 2t$이다.

'유사 바나나 문자열'은 유사 바나나를 하나 이상 이어 붙인 문자열이다. 즉 $B$가 하나 이상 나오는 구간으로 시작하여 $ANANA$를 거치고, 이어서 $NA$가 반복될 수 있는 조각이 하나 이상 연결된 형태이다. $B$, $A$, $N$으로 이루어진 문자열이 주어질 때, 각 위치의 문자를 바꾸어 유사 바나나 문자열로 만드는 데 필요한 바꿈 횟수의 최솟값을 구하라.

길이가 $M$인 문자열 $S$가 한 줄로 주어진다. $S$는 $B$, $A$, $N$ 세 종류의 문자로만 이루어져 있다. $M$은 6 이상 100000 이하이다.

주어진 문자열을 유사 바나나 문자열로 바꾸는 데 필요한 문자 바꿈 횟수의 최솟값을 한 줄로 출력한다. 길이가 6 이상인 모든 입력에 대하여 도달 가능한 유사 바나나 문자열이 존재하므로, 항상 답이 존재한다.

하나의 유사 바나나는 $B$가 하나 이상 오고, 그 뒤에 $ANANA$가 오고, 그 뒤에 $NA$가 0번 이상 반복되는 형태이다. 전체 문자열은 이러한 조각이 끝없이 이어진 것으로 볼 수 있으며, 조각이 끝나는 지점에서는 다음 조각의 첫 문자 $B$와 꼬리 부분의 $N$ 중 하나가 올 수 있다.

이 구조는 상태가 8개인 결정적 유한 오토마톤으로 나타낼 수 있다. 입력 문자열을 이 오토마톤에 맞추는 과정은 각 위치에서 각 상태로 도달하는 최소 바꿈 횟수를 갱신하는 동적 프로그래밍으로 풀 수 있다.