Minimum edit distance of zig zag string

Question

I have string like this xxoxxooo and I wanna edit it to this form xoxoxoxo, my question is how to find minimum number of swaps and I can only swap 2 neighbours as swap. I thought about going through the string and finding the closest redundant x and move it to current place but thats too slow I think, beacuse string can have 1e6 * 2 chars. Any ideas?

Answer 1

You can just ignore one of the types of characters, and count the distance of each of the other type of character to each target position.

More specifically, the i-th occurrence of the chosen type of character will always get mapped to the i-th target position - it would be redundant to move it past that point (as we'd be swapping two of the same type at some point), and if it's not moved to there, there won't be enough of that type of characters on one of the sides. Also, since we can only swap adjacent characters, we take a number of moves equal to exactly the distance to get a character to a position.

This can be done with the following algorithm: (pseudo-code)

distance = 0
pos = 0
for i = 0 to n
  if i == 'x'                     // only check 'x's
    distance += abs(i - pos)      // calculate distance to target position
    pos += 2                      // move to the next position

For your example:

index      0 1 2 3 4 5 6 7
character  x x o x x o o o
distance 0 0 1 1 2 4 4 4 4
pos      0 2 4 4 6 8 8 8 8

So the distance is 4.

Answer 2

Lets denote s_i the swap between position i and i+1

Suppose that you have a minimal swap sequences S = s_{i1} s_{i2} ... going from A to B. Because it is minimal you only swap x with o and never an x with an x or an o with an o. Therefore the action of S is to send the first o of A to the first o of B, the second o of A to the second o of B and so on. Therefore, the number of swap can't be smaller than

Sum_i abs(pos of i-st o in A - pos of i-st o in B)

Now it's easy to find a sequence with exactly this number of swaps this is therefore the correct value.

Here is an algorithm to compute it

Input: s1 and s2 of common length n
I'm assuming that they contains the same number of 'x' and 'o'

res = 0;
i1 = 0; i2 = 0;
while true do
    // find the next o
    while i1 < n and s1[i1] == 'x' do
        i1++
    if i1 == n return res
    // no check that i2 < n because of assumption
    while s2[i2] == 'x' do 
        i2++
    res += abs(i1-i2)
    i1++; i2++