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.

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
>