#MX96. String

String

题目描述

给你一个长度为 nn 的,仅由 AA 和 BB 构成的字符串 SS ,每一次操作你可以将一个 AA 变成一个 BB ,也可以将一个 BB 变成一个 AA 。请你求出最少多少次操作后,可以将这个字符串变成一个非递减的字符串?

非递减是指不存在一对 (i,j)(i,j) ,满足 i<ji<j 且 Si=B,Sj=AS_i=B,S_j=A 。

输入格式

一行一个字符串 SS 。

输出格式

输出一个数字,表示最少的操作次数。

数据规模与约定

对于 20% 的数据,n≤20n\leq 20 。

对于 40% 的数据,n≤100n\leq 100 。

对于 60% 的数据,n≤2000n\leq 2000 。

对于 100% 的数据,1≤n≤106,Si={A,B}1\leq n\leq 10^6,S_i=\{A,B\}

样例

样例 输入样例1 输入

AABBA

样例 输出样例1 输出

1

输入/输出样例2

见下发文件。