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?
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.