top button
Flag Notify
    Connect to us
      Facebook Login
      Site Registration Why to Join

Facebook Login
Site Registration

Minimum number of swaps required to transform one string to other

+5 votes
1,630 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 by Raghu

Share this question
Facebook Share Button Twitter Share Button Google+ Share Button LinkedIn Share Button Multiple Social Share Button

1 Answer

+2 votes

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.

answer Nov 25, 2013 by Sanketi Garg
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
+8 votes

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

0 votes

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

+4 votes

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

Contact Us
+91 9880187415
sales@queryhome.net
support@queryhome.net
#280, 3rd floor, 5th Main
6th Sector, HSR Layout
Bangalore-560102
Karnataka INDIA.
QUERY HOME
...