2

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?

tshepang
  • 12,111
  • 21
  • 91
  • 136
c0ntrol
  • 908
  • 2
  • 9
  • 14

2 Answers2

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++
hivert
  • 10,579
  • 3
  • 31
  • 56
0

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.

Bernhard Barker
  • 54,589
  • 14
  • 104
  • 138
  • I came up with this http://pastebin.com/qbAUMU30, and the result is min(minSwaps(array, size, 0), minSwaps(array2, size, 1)) is it okay? – c0ntrol Feb 03 '14 at 13:53
  • Please ask another question if your code don't work or ask for a review on http://codereview.stackexchange.com/. That being said, the code linked is far from being optimal it has O(n^2) complexity whereas you could have a O(n) by using a trick similar to merge. See the forthcomming edit in my post. – hivert Feb 03 '14 at 14:26
  • @user1295618 If you were trying to follow my pseudo-code (or even if you aren't), you're overcomplicating it a lot - you really only need a single for loop (`pos` should be declared **outside** the loop and incremented inside the if-statement, as in the pseudo-code). – Bernhard Barker Feb 03 '14 at 14:53
  • I followed hivert idea, but here is my implemetation of your idea, but it does not working, http://pastebin.com/eXbcuZ5Q . It gives wrong result by one more. The input is in this form 1 1 1 1 0 0 0 0 , 1 = x, 0 = o – c0ntrol Feb 03 '14 at 15:49