MUTDNA - DNA

no tags 

 

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

 

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
arjundabra: 2014-09-27 13:02:11

please add more test cases
i m getting WA but couldn't find any such case

Martijn Muijsers: 2013-12-05 23:20:24

Nice problem! O(n) complexity and O(1) memory passes!

Miguel Oliveira: 2013-09-07 16:43:19

same algorithm gets TLE in python and accepted in 0.08s in C++ with no optimizations :/


Added by:UNI Training
Date:2012-12-31
Time limit:0.305s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:COCI 2011-2012 Contest #5