>>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(n2), 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
Gregory