Merge Strings

In this approach, We can recursively merge the strings. Since we need to merge the strings in such a way that their relative order is maintained, we can have two pointers ‘AIDX’ and ‘BIDX’ pointing to the first characters of strings ‘A’ and ‘B’ respectively. At any point, we have two options, either we merge the character at ‘A[ AIDX ]’ or we merge the character at ‘B[ BIDX ]’.

 We can recursively try both ways one by one and check which one yields the minimum cost. To check the number of consecutive characters that are not equal we can make a variable that denotes the last character was taken from which string and then we can access the character and check if the current merging character is equal to the previous character or not.

The steps are as follows:-

// Recursive function to find minimum cost

function getMinCostUtil(string& a, string& b, int aidx, int bidx, int lastCh):

1. If indices of string 'A' and 'B' is equal to 'N' and 'M' respectively then return 0.
2. Initialize a variable 'PREV' with 0, it denotes the ASCII value of the last character.
3. If the value of 'lastCh' is 0 then update the value of 'PREV' with the ASCII value of the character at 'AIDX' - 1 from 'A'.
4. Else update the value of 'PREV' with the ASCII value of the character at 'BIDX' - 1 from 'B'.
5. If 'BIDX' is equal to 'M' then recursively call 'getMinCostUtil' with the cost of appending 'A[AIDX]' into the string 'C'.
6. If 'AIDX' is equal to 'N' then recursively call 'getMinCostUtil' with the cost of appending 'B[BIDX]' into the string 'C'.
7. Else recursively call the 'getMinCostUtil' function by first appending  'A[AIDX]' into the string 'C' then restore the string and call the function again by appending 'B[BIDX]' then return the minimum value returned by them.

function getMinCost(string& a, string& b):

1. Call 'getMinCostUtil' first by appending the first character of string  'A' then restore the string and call the function again by appending the first character of 'B', store the minimum of them into the variable  'ANS'
2. Return the value of the variable 'ANS'.

The backtracking approach discussed before can be optimized using memoization. Let a state ‘S’ be defined by  (‘AIDX’, ‘BIDX’, ‘lastCh’), if we observe carefully we are calculating the minimum value for some states (‘AIDX’, ‘BIDX’, ‘lastCh’) many times. We can store the minimum value for each state ‘S’ in a matrix and when we visit it again we will not calculate it but return the value already stored,

Let us define a matrix ‘DP’ of size ‘N’ x ‘M’ x 2. 2 is used as an identifier to detect the last character was taken from which string. ‘DP[ i ][ j ][ k ]’ stores the minimum value calculated for the state ( ‘i’, ‘j’, ‘k’ ).  

The steps are as follows:-

// Recursive function to find minimum cost

function getMinCostUtil(string& a, string& b, int aidx, int bidx, int lastCh, [ [ [ int ] ] ] dp):

1. If indices of string 'A' and 'B' is equal to 'N' and 'M' respectively then return 0.
2. If ‘DP[ AIDX ][ BIDX ][ lastCh ]’ is not equal to -1 then return the value of ‘DP[ AIDX ][ BIDX ][ lastCh ]’.
3. Initialize a variable 'PREV' with 0, it denotes the ASCII value of the last character.
4. If the value of 'lastCh' is 0 then update the value of 'PREV' with the ASCII value of the character at 'AIDX' - 1 from 'A'.
5. Else update the value of 'PREV' with the ASCII value of the character at 'BIDX' - 1 from 'B'.
6. If 'BIDX' is equal to 'M' then recursively call 'getMinCostUtil' with the cost of appending 'A[AIDX]' into the string 'C' and store the value returned in ‘DP[ AIDX ][ BIDX ][ lastCh ]’.
7. If 'AIDX' is equal to 'N' then recursively call 'getMinCostUtil' with the cost of appending 'B[BIDX]' into the string 'C' and store the value returned in ‘DP[ AIDX ][ BIDX ][ lastCh ]’.
8. Else recursively call the 'getMinCostUtil' function by first appending  'A[ AIDX ]' into the string 'C' then restore the string and call the function again by appending 'B[BIDX]' then store the minimum value returned by them in  ‘DP[ AIDX ][ BIDX ][ lastCh ]’ and return it.

function getMinCost(string& a, string& b):

1. Initialize a 3d matrix ‘DP’ of size ‘N’ x ‘M’ x 2 with -1.
2. Call 'getMinCostUtil' first by appending the first character of string  'A' then restore the string and call the function again by appending the first character of 'B', store the minimum of them into the variable  'ANS'
3. Return the value of the variable 'ANS'.

The idea is the same as memoization. We are going to use the recurrence relation used in memoization. 

The steps are as follows:-

function getMinCost(string& a, string& b):

1. Initialize a 3d matrix ‘DP’ of size ‘N’ x ‘M’ x 2 with -1.
2. Set 'DP[1][0][0]' and 'DP[0][1][1]' to 1.
3. Run a loop from 'i' = 0...'N':
   • Run a loop from 'j' = 0...'M'
     • If 'i' < 'N':
       • If 'i' > 0 then update the value of 'DP[ i+1 ] [ j ][ 0 ]' to the minimum of 'DP[ i+1 ][ j ][ 0 ]' and ('DP[ i ][ j ][ 0 ]' + (‘A[ i-1 ]’ != ‘A[ i ]’)).
       • If 'j' > 0 then update the value of 'DP[ i+1 ][ j ][ 0 ]' to the minimum of 'DP[ i+1 ][ j ][ 0 ]' and ('DP[ i ][ j ][ 1 ]' + ('B[ j-1 ]' != 'A[ i ]' )).
     • if 'j' < 'M':
       • If 'i' > 0 then update the value of 'DP[ i ][ j+1 ][ 1 ]' to the minimum of 'DP[ i ][ j+1 ][ 1 ]' and ('DP[ i ][ j ][ 0 ]' + ('A[ i-1 ]' != 'B[ j ]')).
       • If 'j' > 0 then update the value of 'DP[ i ][ j+1 ][ 1 ]' to the minimum of 'DP[ i ][ j+1 ][ 1 ]' and ('DP[ i ][ j ][ 1 ]' + ('B[ j-1 ]'!= 'B[ j ]' ))
4. Return the minimum of 'DP[n][m][0]' and 'DP[n][m][1]'.