MUTDNA  DNA
Biologists have discovered a strange DNA molecule, best described as a sequence of N characters from
the set {A, B}. An unlikely sequence of mutations has resulted in a DNA strand consisting only of A's.
Biologists found that very odd, so they began studying the mutations in greater detail.
They discovered two types of mutations. One type results in changing a single character of the
sequence (A → B or B → A). The second type changes a whole prefix of the sequence, specifically
replacing all characters in positions from 1 to K (for some K between 1 and N, inclusive) with the other
character (A with B, B with A).
Compute the least possible number of mutations that could convert the starting molecule to its end
state (containing only A characters). Mutations can occur in any order
Input
The first line of input contains the positive integer N (1 ≤ N ≤ 1 000 000), the length of the molecule.
The second line of input contains a string with N characters, with each character being either A or B.
This string represents the starting state of the molecule.
Output
The first and only line of output must contain the required minimum number of mutations.
Example
Input 1: 4 ABBA Output 1: 2
Input 2: 5 BBABB Output 2: 2
Input 3: 12 AAABBBAAABBB Output 3: 4
hide comments
hello_world123:
20180712 20:54:49
Can be solved using DP too...; ) 

arjundabra:
20140927 13:02:11
please add more test cases


Martijn Muijsers:
20131205 23:20:24
Nice problem! O(n) complexity and O(1) memory passes! 

Miguel Oliveira:
20130907 16:43:19
same algorithm gets TLE in python and accepted in 0.08s in C++ with no optimizations :/ 
Added by:  UNI Training 
Date:  20121231 
Time limit:  0.305s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  COCI 20112012 Contest #5 