Given two strings s1 and s2, the task is to find the minimum number of steps required to convert s1 into s2. The only operation allowed is to swap adjacent elements in the first string. Every swap is counted as a single step.
Examples:
Input: s1 = “abcd”, s2 = “cdab”
Output: 4
Swap 2nd and 3rd element, abcd => acbd
Swap 1st and 2nd element, acbd => cabd
Swap 3rd and 4th element, cabd => cadb
Swap 2nd and 3rd element, cadb => cdab
Minimum 4 swaps are required.
Input: s1 = “abcfdegji”, s2 = “fjiacbdge”
Output:17
There is a GFG post present for the same question. The time complexity on the post is O(n^2).
GFG post link: https://www.geeksforgeeks.org/minimum-number-of-adjacent-swaps-to-convert-a-string-into-its-given-anagram/
Question is can it be solved in better time complexity.
Thanks in advance.
Related blog
First make a permutation that for each character store the nearest place it will go in the second string, then count the number of inversions of it using BIT or Trie or mergesort tree.
For example :
$$$s = abcd$$$ and $$$t = cdab$$$
The permutation will be this: $$$[3, 4, 1, 2]$$$
So the number of inversions of this array will be $$$4$$$ and that is the answer.
Time complexity is $$$O(NlogN)$$$.
thanks for sharing the approach, I get it now, So basically, when the permutation becomes-[3,4,1,2], now we just have to find minimum adjacent swaps to sort the array and that would be equal to number of inversions.
You also have to handle equal characters. This is explained in the "related blog".