Merge Strings

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
3 upvotes
Asked in companies
1 Silver Bullet TechGoogle inc

Problem statement

You are given two strings ‘A’ and ‘B’ of length ‘N’ and ‘M’ respectively. You need to construct a new string ‘C’ by merging both strings in such a way that the relative order of characters in ‘A’ and ‘B’ is the same in string ‘C’.

For example, if the string ‘A’ is of length 3 then the first character of string ‘A’ should be placed before the second and third characters of string ‘A’ in string ‘C’. Similarly, the second character of string ‘A’ should be placed after the first character and before the third character of string ‘A’ in string ‘C’.

The cost of merging the strings is given by the number of consecutive characters in string ‘C’ that are not equal + 1, i.e. ‘C[ i ] != ‘C[ i + 1]’.

Find the minimum cost of merging both strings.

Example: 
Input: ‘N’ = 3, ‘M’ = 3, ‘A’ = aba, ‘B’ = aab 

Output: 3

One of the valid strings with minimum cost after merging ‘A’ and ‘B’ is ‘aaabba’. The order of characters of string ‘A’ as well as ‘B’ is maintained in the string ‘aaabba’ and the cost of this string is (1 + 2) = 3.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line will contain the integer 'T', denoting the number of test cases.

The first line of each test case contains two integers ‘N’ and ‘M’ denoting the length of strings ‘A’ and ‘B’ respectively’.

The second line of each test case contains the string ‘A’.

The third line of each test case contains the string ‘B’.
Output format : 
For each test case, you don’t need to print anything just return the minimum cost of merging strings ‘A’ and ‘B’.
Note : 
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= N <= 5000
1 <= M <= 5000

Sum of N Over all the Test cases <= 5000
Sum of M Over all the Test cases <= 5000

Time Limit: 1 sec
Sample Input 1 :
2
4 4
aaaa
bbbb
3 3
abc
def
Sample Output 1 :
2
6
Explanation Of Sample Input 1 :
For the first case:
One of the valid strings with minimum cost is “aaaabbbb”. The cost of this string is ( 1 + 1 ) = 2.

For the second case:
One of the valid strings with minimum cost is “abcdef”. The cost of this string is ( 1 + 5 ) = 6
Sample Input 2 :
2
3 4
ahu
huaa
4 3
abaa
aab
Sample Output 2 :
4 
3
Hint

Can you think of a way to generate all possible strings recursively and then choose the one with minimum cost?

Approaches (3)
Recursion

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'.
Time Complexity

O( 2^( N + M ) ), Where ‘N’ and ‘M’ are the lengths of the strings ‘A’ and ‘B’ respectively.

 

For any ‘i’th character in ‘C’, we have two choices of either merging the character of ‘A’ or the character of ‘B’. We are exploring both the ways recursively, so the recursive tree grows as 1, 2, 4, … 2^( N + M) because the length of the string should be ( ‘N’ + ‘M’ ).

Hence the time complexity is O( 2^( N + M )  ).

Space Complexity

O( N + M ), Where ‘N’ and ‘M’ are the lengths of the strings ‘A’ and ‘B’ respectively.

 

The height of the recursive tree can be at most ( ‘N’ + ‘M’ ).

Hence space complexity is O( N + M ).

Code Solution
(100% EXP penalty)
Merge Strings
Full screen
Console