Transform One String to Another with a Minimum Number of Operations

Posted by N.K. Chauhan on Mar 31, 2024

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).

Related


Check if two given strings are isomorphic to each other

Check if two strings are equal or not after processing backspace

Reverse words in a given string

Check whether the given string is a palindrome

Find all substrings of a string in "O (n^2)" time

Power Set: Print all non-empty subsequences of a string

Print all permutations of a given string

Print all subsequences of a string

Swap all occurrences of two characters to get lexicographically smallest string

Longest Common Prefix in an Array of Strings