swordx's blog

Minimum adjacent swaps to make strings equal
By swordx, history, 2 years ago, In English

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.

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Related blog

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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 :

Unable to parse markup [type=CF_MATHJAX]

and

Unable to parse markup [type=CF_MATHJAX]

The permutation will be this:

Unable to parse markup [type=CF_MATHJAX]

So the number of inversions of this array will be $$$4$$$ and that is the answer.

Time complexity is $$$O(NlogN)$$$.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      You also have to handle equal characters. This is explained in the "related blog".

      → Reply