Editorial for JDCC '16 Contest 3 P3 - Letter Swap
Submitting an official solution before solving the problem yourself is a bannable offence.
First reverse the given string. We'll call the original string and the target string . It doesn't matter which string is which since moving it from the original to the target and back takes the same amount of swaps. As such, in this editorial, I may change the target into the original.
Now consider the problem like this:
0s are blank, and you can move the
1s. Each time you move a
1 you use one swap. Now iterate through string . If there is a
1, you find the next
1 on string to move. Note that the order does matter. The first
1 should also the be first
1 of the reversed string.
The problem just becomes finding the differences between the indices of each
1. For example, if there is a
1 at index , and its respective
1 is at index , then you would need to use \(\lvert 7 - 3\rvert = 4\) swaps. To do this, you have two lists containing the indices of the
1s of the two strings. Generate these lists by iterating each string and inserting the index into the list if it is a
1. The total number of swaps required is the sum of absolute differences of all pairs of indices.
Time Complexity: , where is the length of the string.