This task can be solved using dynamic programming. Let ~f(K)~ be the smallest number of mutations needed to convert the first ~K~ characters to A. Conversely, let ~g(K)~ be the smallest number of mutations needed to convert the first ~K~ characters to B.

If the ~K^\text{th}~ character is already equal to A, then obviously ~f(K) = f(K-1)~.

On the other hand, if the ~K^\text{th}~ character is equal to B, we have two options:

1. Change the ~K^\text{th}~ characters using a first-type mutation, giving ~f(K-1)+1~ mutations;

2. Change the prefix of length ~K~ (second-type mutation); in this case, we first need to convert the first ~K-1~ characters to B (in order to convert them all to A using the prefix mutation), which requires ~g(K-1)~ mutations, resulting in a total of ~g(K-1)+1~ mutations.

Therefore, if the ~K^\text{th}~ character is equal to B, then ~f(K) = \min\{f(K-1)+1, g(K-1)+1\}~.

We also need to derive analogous relations for ~g(K)~.

Now the problem can be easily solved by calculating ~f(1)~, ~g(1)~, ~f(2)~, ~g(2)~ and so on until obtaining the result ~f(N)~.

The problem has another, simpler solution. We can iterate over the string backwards, converting each encountered character to A. If we find an A, we can simply continue. However, if we find a B, we have to decide which mutation to use. It turns out that a correct strategy is to look at the character in front of B. If A precedes the current B, then we convert only the B, and if another B precedes the current B, we convert the whole prefix. The proof of correctness of this algorithm, as well as a trick to quickly flip the whole prefix, is left as an exercise to the reader.