Given two strings, s1 and s2, of length n1 and n2.
The task is to determine if the first string can be transformed into the second string. If so, find the minimum number of operations required for the transformation.
The only operation allowed is to remove any character from s1 and insert it at the front.
If transformation is not required, return "0" and if not possible, return "-1".
Input: s1 = "EACBD", s2 = "EABCD"
Output: 3
Input: s1 = "ABD", s2 = "BAD"
Output: 1
Solutions
Method 1: Recursive
One string s1 can be transformed into another string s2 if both strings have the same number of characters and the same set of characters.
This can be easily checked by creating a count array for the first string and checking if the second string has the same count of every character.
Every character in a string can be represented as a numeric ASCII code. ASCII ranges from 0 to 255 in decimal.
Now we need to find the minimum number of operations needed to transform s1 to s2.
The idea is to start matching from the last characters of both strings.
If the last characters match, then our task reduces to n-1 characters.
If the last characters don't match, then find the position of s2's mismatched character in s1.
For every mismatch, we need to replace one character, hence adding +1 to operations.
Complexity
The time complexity of this solution is O(n) and space complexity is O(1).
Method 2: Iterative
One string s1 can be transformed into another string s2 if both strings have the same number of characters and the same set of characters.
This can be easily checked by creating a count array for the first string and checking if the second string has the same count of every character.
Every character in a string can be represented as a numeric ASCII code. ASCII ranges from 0 to 255 in decimal.
Now we need to find the minimum number of operations needed to transform s1 to s2.
The idea is to start matching from the last characters of both strings.
If the last characters match, then our task reduces to n-1 characters.
If the last characters don't match, then find the position of s2's mismatched character in s1.
For every mismatch, we need to replace one character, hence adding +1 to operations.
Complexity
The time complexity of this solution is O(n) and space complexity is O(1).