Last Updated: 10 Dec, 2020

String Maker

Hard

Asked in companies

Solve now

Problem statement

According to Ancient Ninjas, string making is a form of art. There are various methods of string making, one of them uses previously generated strings to make the new one. Suppose you have two strings A and B, to generate a new string C, you can pick a subsequence of characters from A and a subsequence of characters from B and then merge these two subsequences to form the new string.

Though while merging the two subsequences you cannot change the relative order of individual subsequences. What this means is - suppose there are two characters ‘Ai’ and ‘Aj’ in the subsequence chosen from ‘A’, where i < j, then after merging, if i acquires position k and j acquires p then k < p should be true and the same apply for subsequence from B.

Given strings ‘A’, ‘B’, ‘C’ can you count the number of ways to form string ‘C’ from the two strings ‘A’ and ‘B’ by the method described above? Two ways are different if any of the chosen subsequences is different.

As the answer could be large so return it after modulo 10 ^ 9 + 7.

For Example :

let A = a, B = ac, C = ac.

Now In this example, we can take whole string B to form C or take substring {a} and substring {c} from A and B, respectively to make C. Hence the answer is 2.

Input Format :

The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then each test cases follow.

The first line of each test case contains a string ‘A’.

The Second line of the test case contains the string ‘B’.

The third line of the test case contains the string ‘C’.

Output Format :

For each test case, print a single integer ‘ANS’ representing the number of ways.

Output for each test case will be printed in a separate line.

Note :

You are not required to print anything; it has already been taken care of. Just implement the function and return the answer.

Constraints :

1 <= T <= 5
1 <= |A|, |B|, |C| <= 100, where |S| represents the length of the String S.

Time limit: 1 sec

Solve now

Approaches

01 Approach

The basic idea is to go through every element of the string A and B and check if the current element equals any element at some position in string C.

The steps are as follows:

Create a function ‘recursion’ in which we will pass all the strings and their string length x, y, z for strings A, B, C, respectively.
In the ‘recursion’ function:
1. Iterate through the string A from x to 0:(say iterator be i):
  1. If the current element at x of A is equal to the current element at z of C call the function for position x-1, y, z-1 and add it to the total ways.
2. Similarly, iterate through the string B from y to 0:(say iterator be i):
  1. If the current element at y of B is equal to the current element at z of C call the function for position x, y-1, z-1 and add it to the total ways.
3. Return the total ways.
In the ‘Main’ function:
1. Call the ‘recursion’ function.

Solve now

02 Approach

This approach is same as the naive approach. The only difference is we will store all the results in an array dp to avoid repetitions.

The steps are as follows:

Create a function ‘memoization’ in which we will pass all the strings and their string length x, y, z for strings A, B, C, respectively.
In the ‘memoization’ function:
1. Return dp[ x ][ y ][ z ] if dp[ x ][ y ][ z ] is not equal to -1.
2. Iterate through the string A from x to 0:(say iterator be i):
  1. If the current element at x of A is equal to the current element at z of C call the function for position x-1, y, z-1 and add it to dp[ x ][ y ][ z ].
3. Similarly, iterate through the string B from y to 0:(say iterator be i):
  1. If the current element at y of B is equal to the current element at z of C call the function for position x, y-1, z-1 and add it to dp[ x ][ y ][ z ].
4. Return dp[ x ][ y ][ z ].
In the ‘Main’ function:
1. Initialize a 3D dp of size X, Y, Z and initially make all the elements of the dp -1.
2. Call the ‘recursion’ function.
3. Return dp[ x ][ y ][ z ].

Solve now

03 Approach

In this approach, we will iterate over both the strings and check if the current element of the string matches with the current element of the final string and update the dp array.

Initialize a 3D array dp of size (X + 1)*(Y + 1)*(Z + 1) with value 0, where X, Y, Z is the size of strings A, B, C, respectively.
Update the value of dp array with 1 for all positions of X and Y when Z is zero.
Iterate in a loop for string A from 1 to X(say iterator be i) :
1. Iterate in a for loop for string B from 1 to Y(say iterator be j) :
  1. Iterate in a for loop for string C from 1 to Z(say iterator be k) :
    1. Iterate from 1 to i(say iterator be t) and check if A[t - 1] is equal to C[k - 1] :
      1. Update dp[ i ][ j ][ k ] with dp[ t - 1 ][ j ][ k - 1 ].
    2. Similarly, Iterate from 1 to j(say iterator be t) and check if B[t - 1] is equal to C[k - 1]:
      1. Update dp[ i ][ j ][ k ] with dp[ i ][ l - 1 ][ k - 1 ].
Return dp[ x ][ y ][ z ].

Solve now