>>Fabio,
>>
>>Your "do not move anything" assumption is not right, it is not how the current code works. It would require moving AAAAABB, then AAAAAB, then AAAAA.
>>
>>There do exist other input strings that require more movement when proccessed right to left, it is a shame that you don't see this fact.
>>
>>But the whole underlying fallacy of moving the same character more than once in any algorithm is what makes it O(n²), which is a foolish waste of CPU time when it can be done O(n) as I've posted in the C++ code.
>>
>
>Someone has the patience to explain as the thing to David works.
>Thanks.

I see the difference Fabio.

In a right to left you never move a char too many, ie one that you will discard later, you move processed data

In a left to right you are likely to move chars that you will discard later, you move non processed data

Left >> right = move chars that will not necessarily be in the end result


Right >> left = never move chars that are not in the end result

eg: take * out

12*4*6*89

Left >> right
move 1: 4*6*89   6 chars  where 2 not in the end result
move 2: 6*89     4 chars  where 1 not in the end result
move 3: 89       2 chars  where 0 not in the end result
                ---
                12 chars  where 3 not in the end result

Right to left

move 1: 89       2 chars where 0 not in the end result
move 2: 689      3 chars where 0 not in the end result
move 3: 4689     4 chars where 0 not in the end result
                ---
                 9 chars where 0 not in the end result