# Minimum number of swaps required to transform one string to other

1,853 views

Given 2 strings s1, s2 and s1 is equal to s2 if they are lexicographically sorted, Find minimum number of swaps required to transform s1 to s2?

Swap Definition:
Problem 1 : we can transform index i with i+1 where 0<=i< s1.length()-1
Problem 2 : we can transform index i with i+1 where 0<=i< s1.length()-1 and other operation we can swap first character of string with last

example: s1="abc", s2="cba"
In problem1 3 swaps required abc ---> bac ---> bca ---> cba
In problem2 1 swaps required abc ---> cba [swap first and last element]

posted Nov 25, 2013

For any given index, if the characters in both the strings are not equal. There is a mismatch. Since the mismatched character from first string will cause a mismatch in the second string at another position j. So the total number of mismatches will always be a multiple of 2.

One swap corrects position of 2 characters. So the optimal number of mismatches is half the total number of mismatches.

I understand about that, But i need an algorithm(procedure) for finding minimum number of swaps
Finding the  minimum number of swaps is easy -
1. Start a loop till length
2. compare a[i] with b[i]
3. if both are not equal increase the count by 1
4. In the end return count/2
Considering two scenarios here

1. We are counting swaps without actually swapping elements ( not sure if above algorithm will work)
2. We are counting swaps with swapping elements. I think in this case count would be minimum swap count rather swap.

Please correct me if I'm wrong.
Similar Questions

Convert the given string into palindrome with minimum number of appends(at end of the given string). O(n) algorithm will be appreciated ??

Input :=> Malayal
Output :=> Malayalam

WAP to find the minimum number of swaps required for arranging pairs adjacent to each other?

Input:
pairs[] = {1->3, 2->6, 4->5} // 1 is paired with 3, 2 with 6 ...
arr[] = {3, 5, 6, 4, 1, 2}

Output:
2
{3, 1, 5, 4, 6, 2} by swapping 5 & 6, and 6 & 1

How to convert one string to another such that only one character is changed at a time and after each change the transformed string is in the dictionary. You need to do this in the minimum number of transformations. For example the transformation from rat-->boy can be done as follows:

rat-->bat-->bot-->boy (if dictionary has bat and bot)

Any suggestion on how to achieve this?

+1 vote

Given a string and dictionary of words, form a word by removing minimum number of characters.
Characters can be removed in-order only.

+1 vote

Given an array of denominations and array Count , find minimum number of coins required to form sum S.

for example:

coins[]={1,2,3};
count[]={1,1,3};

i.e we have 1 coin of Rs 1 , 1 coin of Rs 2 , 3 coins of Rs 3.

Now if we input S = 6 then output should be 2 with possible combination : 3+3 = 6