String Maker

Hard
0/120
Average time to solve is 50m
profile
Contributed by
18 upvotes
Asked in companies
GrofersCRED

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
ab
ab
ab
xy
wz
wxzy
Sample Output 1:
4
1
Explanation For Sample Output 1:
For the first test case, 
A = {ab}, B = {}
A = {a}, B = {b}
A = {b}, B = {a}
A = {}, B = {ab}
These are the four possible combinations. Hence the answer is 4.

For the second test case, there is only one way possible i.e. A = {xy}, B = {wz}. Hence the answer is 1.
Sample Input 2:
2
abc
abc
abc
tx
qs
xt
Sample Output 2:
8
0
Hint

Try every possible way to form string C.

Approaches (3)
Naive 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:

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

Z * (X! + Y!), where X, Y, Zs is the length of string A, B, C respectively.


Since we are iterating through every possible substring of A and B. Hence the time complexity is Z * (X! + Y!).

Space Complexity

O(1).

 

Since we are not taking any extra space. Hence the space complexity is O(1).

Code Solution
(100% EXP penalty)
String Maker
Full screen
Console