Find minimum operations required to transform a string into another string

Given two strings, determine if the first string can be transformed into the second string. The only operation allowed is to move any character from the first string to the front. If the string can be transformed, find the minimum number of operations required for the transformation.


 

For example, the minimum number of operations required to convert the string ADCB to string ABCD are 3.


ADCB -> CADB (Move C to the front)
CADB -> BCAD (Move B to the front)
BCAD -> ABCD (Move A to the front)

 
1. To determine if a string can be transformed into another string, check whether both strings have same set of characters. If both strings have different set of characters, they can’t be transformed.

 
2. To find the minimum number of operations required to convert the first string to the second string, the idea is to simultaneously traverse both strings from the end. If the last characters of both strings match, then move to the next pair of characters. If the last character of both strings donโ€™t match, then we find the index of the matching character in the first string. The difference between both indices represents the number of characters in the first string that has to be moved before current character of the first string.

 

Download ย  Run Code

Output:

Minimum operations required to convert the string ADCB to string ABCD are 3

 
The time Complexity of above solution is O(n) and auxiliary space required by the program is O(n).

 
1 Star2 Stars3 Stars4 Stars5 Stars (2 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding ๐Ÿ™‚
 


Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
viperx
Guest

how its working can you explain it with more detail

Anil
Guest

ABCDE -> ACBED

Can someone explain this conversion as per the code.
I see it should take only 2 operations, but the given code is giving more than 2

–Anil