Given two strings, determine if the first string can be transformed into the second string. The only operation allowed is moving a 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 is 3.

ADCB —> CADB (Move ‘C’ to the front)
CADB —> BCAD (Move ‘B’ to the front)
BCAD —> ABCD (Move ‘A’ to the front)

Practice this problem

1. To determine if a string can be transformed into another string, check whether both strings have the same set of characters. If both strings have a 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, move to the next pair of characters. If the last character of both strings doesn’t match, 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 the current character of the first string.

 
The algorithm can be implemented as follows in C++, Java, and Python:

C++


Download  Run Code

Output:

The minimum operations required to convert the string ADCB to string ABCD are 3

Java


Download  Run Code

Output:

The minimum operations required to convert the string ADCB to string ABCD are 3

Python


Download  Run Code

Output:

The minimum operations required to convert the string ADCB to string ABCD are 3

The time complexity of the above solution is O(n) and requires O(n) extra space, where n is the length of the input string.