*Bounty: 50*

*Bounty: 50*

Suppose we have a binary string $s$. We wish to partition this string in a series of $0$s followed by $1$s (alternatively: we wish to sort), using only one operation: moving three consecutive elements to the end.

E.g. if our string is $ABCDEFGH$ we can do our operation at index $1$ to get $DEFGHABC$. If we did it at index $4$ we’d get $ABCGHDEF$.

I’m interested in optimal solutions – that is with the least amount of moves. I have a working algorithm using IDA* with heuristic “# of groups of ones with length $leq 3$ before the final zero”, with the logic that each such a group requires at least one move to fix. An example optimal solution (where `^`

indicates where a block was chosen to move to the end):

```
1101101011101011010010010011
^
1101101011101011010010011100
^
1101101011101011010011100001
^
1101101011101010011100001110
^
1101101011110011100001110010
^
1101101011110011100001110001
^
1101111110011100001110001010
^
1111110011100001110001010011
^
1111110011100001110000011101
^
1111110011100001110000001111
^
1111110011100000000001111111
^
1111110000000000001111111111
^
1110000000000001111111111111
^
0000000000001111111111111111
```

However, this algorithm is exponential and not feasible for larger strings. After studying quite some optimal solutions, especially tough ones like above, I can’t immediately think of an optimal algorithm. Moves can be quite non-trivial.

Is there a feasible optimal algorithm? Or is this problem hard?