>Fabio,
>
>>???? David, I have some doubt
>
>Sure, in that one particular case moving right to left there are less moves in the brute force method.
>
>Remove B from this string: AAAAABBB. Left to right can be done in 3 moves. Right to left requires 18 moves in the brute force method you propose.

Incredible !

Left to right is done with 3 moves.
My right to left is done with 0 moves !

Step 1 'AAAAABBB' remove righ B and do not move enything
Step 2 'AAAAABB' remove righ B and do not move enything
Step 3 'AAAAA' remove righ B and do not move enything
End

>
>But in general processing the string left to right or right to left is equivalent.
>
>If you'd take a bit of time to look at the C++ code on my page, the O(n) can be accomplished by realizing that as you process the string the character can be moved move than one position at a time. This is easily done via running an input pointer and an output pointer along the string.
>
>>

>>'ABABABA'
>>remove B
>>* on place left to right
>>'A'+move 5 chars -> 'AABABA'
>>'AA'+ move 3 chars -> 'AAABA'
>>'AAA'+ move 1 chars -> 'AAAA'
>>* end with 5+3+1 = 9 chars moved
>>
>>* on place right to left
>>'ABABA' + move 1 chars -> 'ABABAA'
>>'ABA'   + move 2 chars -> 'ABAAA'
>>'A'     + move 3 chars -> 'AAAA'
>>* end with 1+2+3 = 6 chars moved
>>