Question

When transforming word u[1 : i] to v[1 : j], in addition to adding, removing, or changing a letter, suppose we also allow for the swapping of adjacent letters. For example, transforming u = tera to v = tear requires a single edit that swaps the ‘r’ with the ‘a’. Provide the recurrence for d(i, j) that occurs when one performs this edit.

Answer 1

Given two strings s1 and s2, the task is to find the minimum number of steps required to convert s1 into s2. The only operation allowed is to swap adjacent elements in the first string. Every swap is counted as a single step.

Examples:

Input: s1 = “abcd”, s2 = “cdab”
Output: 4
Swap 2nd and 3rd element, abcd => acbd
Swap 1st and 2nd element, acbd => cabd
Swap 3rd and 4th element, cabd => cadb
Swap 2nd and 3rd element, cadb => cdab
Minimum 4 swaps are required.

Input: s1 = “abcfdegji”, s2 = “fjiacbdge”
Output:17
Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Approach: Use two pointers i and j for first and second strings respectively. Initialise i and j to 0.
Iterate over the first string and find the position j such that s1[j] = s2[i] by incrementing the value to j. Keep on swapping the adjacent elements j and j – 1 and decrement j until it is greater than i.
Now the ith element of the first string is equal to the second string, hence increment the value of i.
This technique will give the minimum number of steps as there are zero unnecessary swaps.