DNA-AND-DNA
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 115 Accepted Submission(s) : 54
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
生物学家们发现了一个奇怪的DNA分子，可以将它们看作一个由集合{A，B} 中的元素组成的N个字符的序列。由于一系列的突变使得DNA链只包含A。生物学家发现这很奇怪，所以他们开始研究更详细的基因突变。他们发现了两种类型的基因突变。一种类型是改变单个字符的序列（A→B或B→A）。第二类改变了整个序列的前缀，从1到K（1和N之间）。计算数量尽可能少的突变，可以是起始分子转化到它的最终状态（只包含A字符）。突变可以在任何顺序发生。
Input
输入有多组数据。输入的第一行包含一个正整数N（1≤N≤1000 000），表示分子的长度。输入第二行包含N个字符的字符串，这个字符串由A或B组成，表示DNA分子的起始状态。
Output
输出的一行表示必须的最低数量的突变。
Sample Input
4 ABBA 5 BBABB 12 AAABBBAAABBB
Sample Output
2 2 4
Source
2012暑假集训