String Maker

Posted: 10 Dec, 2020
Difficulty: Hard

PROBLEM STATEMENT

Try Problem

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
Approach 1

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:

  1. 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.
  2. 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.
  3. In the ‘Main’ function:
    1. Call the ‘recursion’ function.
Try Problem