Ninja and Strings

Moderate
0/80
3 upvotes
Asked in company
Uber

Problem statement

Ninja found an old book having ‘N’ strings of equal length. By reading all these strings, Ninja thought of a ‘TARGET’ string in his mind and wanted to form this target string using these ‘N’ strings. The formation of the string should follow the following conditions:

1. The indices of characters in the order in which they are used should form a strictly increasing order.
2. You can use multiple characters from one string.

Your task is to find the total number of ways in which the ‘TARGET’ string can be formed. Two ways are said to be different if the sequence of indices is different or the sequence is the same but chosen from different strings. The number of ways can be very large so return its mod 10^9 + 7.

For Example 
For the given ‘WORDS’ = [ "acca","bbbb","caca" ], and ‘TARGET’ = "aba".
There are 6 ways to form the ‘TARGET’ string.
"aba" -> index 0 ("acca"), index 1 ("bbbb"), index 3 ("caca")
"aba" -> index 0 ("acca"), index 2 ("bbbb"), index 3 ("caca")
"aba" -> index 0 ("acca"), index 1 ("bbbb"), index 3 ("acca")
"aba" -> index 0 ("acca"), index 2 ("bbbb"), index 3 ("acca")
"aba" -> index 1 ("caca"), index 2 ("bbbb"), index 3 ("acca")
"aba" -> index 1 ("caca"), index 2 ("bbbb"), index 3 ("caca")
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains a single integer, 'N’, denoting the number of strings in the ‘WORDS’ array.

The second line contains ‘N’ strings denoting the ‘N’ strings found in the book.

The third line contains the ‘TARGET’ string.
Output Format: 
For each test case, print an integer corresponding to the number of ways to form the ‘TARGET’ string  % (10^9 +7).  

Print the output of each test case in a separate line.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N <= 1000.
1 <= length of strings in ‘WORDS’ array<=1000.
1 <= length of ‘TARGET’ string <= length of WORDS[i] .  

Time limit: 1 sec
Sample Input 1:
2
3
adc
aec 
efg
ac  
3
acca
bbbb
caca
aba
Sample Output 1:
4
6
Explanation of sample input 1:
For the first test case,

The possible ways to form the ‘TARGET’ string are:
"ac" -> index 0 ("adc"), index 2 ("adc")
"ac" -> index 0 ("acca"), index 2 ("aec") 
"ac" -> index 0 ("aec"),  index 2 ("adc")
"ac" -> index 0 ("aec"), index 2 ("aec")    

Hence, the answer is 4. 

For the second test case:

The possible ways to form the ‘TARGET’ string are:
"aba" -> index 0 ("acca"), index 1 ("bbbb"), index 3 ("caca")
"aba" -> index 0 ("acca"), index 2 ("bbbb"), index 3 ("caca")
"aba" -> index 0 ("acca"), index 1 ("bbbb"), index 3 ("acca")
"aba" -> index 0 ("acca"), index 2 ("bbbb"), index 3 ("acca")
"aba" -> index 1 ("caca"), index 2 ("bbbb"), index 3 ("acca")
"aba" -> index 1 ("caca"), index 2 ("bbbb"), index 3 ("caca")

Hence, the answer is 6.
Sample Input 2:
2
1
abcd
abcd
2
abba
baab
bab
Sample Output 2:
1
4
Hint

Try to create the ‘TARGET’ string and find the ways using the frequency of characters.

Approaches (3)
Recursion

In this approach, we will declare a recursive function HELPER(‘CUR’, ‘IDX’,’ FREQ’,’TARGET’) that will return the number of the ways to create the substring of ‘TARGET[0..CUR]’. ‘IDX’ represents the current position in ‘WORDS’ array. ’FREQ’ is a 2-D matrix as ‘FREQ[i][c]’ represents the count of character ‘c’ at index ‘i’ in strings of ‘WORDS’ array. 

 

The base case will be if CUR is equal to the length of ‘TARGET’, return 1.

 

And if ‘IDX’ is equal to the length of the string in the ‘WORDS’ array, we don’t have any characters left, so return 0.

 

The answer for this sub-problem will be HELPER(‘CUR’,’IDX’+1,’FREQ’,’TARGET’) (Skipping the ‘IDX’ index of ‘WORDS’) + FREQ[ ‘IDX’ ][ ‘TARGET’[‘CUR’] - ‘a’]*HELPER(‘CUR’+1,’IDX’+1’, FREQ’,’ TARGET’)(Using the characters at ‘IDX’ index of ‘WORDS’).  
 

We will first compute our ‘FREQ’ array to store the frequency of each character at specific indices of ‘WORDS’.At last, we will return HELPER(0,0,’FREQ’,’ TARGET’).

  

Algorithm:

  • Defining function HELPER(‘CUR’, ’IDX’, ’FREQ’,’ TARGET’).
    • If ‘CUR’ is equal to the length of ‘TARGET’, return 1. (Base Case.)
    • If ‘IDX’ is equal to the length of ‘TARGET’, return 0. (Base Case).
    • Declare ‘ANS’ to store the answer to this sub-problem.
    • Set ‘ANS’ as HELPER(‘CUR’, ’IDX’ + 1, ’FREQ’,’ TARGET’).
    • Set ‘ANS’ as ( ANS + (HELPER(‘CUR’, ’IDX’, ’FREQ’,’ TARGET’) * FREQ[ ‘IDX’ ][TARGET[CUR] - ‘a’]) % (10^9 + 7) ) % (10^9 + 7).
    • Return ‘ANS’.
  • Declare a 2-D matrix ‘FREQ’ of size[ length of WORDS[0] ][26] to store the frequency of character ‘C’ at ‘i’th index in ‘WORDS’ array as ‘FREQ’[i][‘C’].
  • Initialize all values of ‘FREQ’ with 0.
  • For each ‘WORD’ in ‘WORDS’, do the following:
    • For each index ‘i’ in the range from 0 to length of  ‘WORD’, do the following:
      • Set FREQ[i][WORD[i]- ‘a’] = FREQ[i][WORD[i]- ‘a’] + 1.
  • Set ‘ANS’ as HELPER(0,0, ’FREQ’, ’TARGET’).
  • Return ‘ANS’.
Time Complexity

O(2^(M*K)), where ‘M’ is the length of the string in the ‘WORDS’ array and ‘K’ is the length of the ‘TARGET’ array.

 

In this approach, we are using a recursive function, and each function call does two more recursive calls. So the total number of recursive calls is of the order 2^(K*M) and. Hence the overall time complexity is O( 2^(M*K)).

Space Complexity

O(2^(M*K)), where ‘M’ is the length of the string in the ‘WORDS’ array and ‘K’ is the length of the ‘TARGET’ array.

 

In this approach, in the worst case, there will be 2^(M*K) recursive calls of function HELPER(). So the stack memory used is of the order 2^(M*K) and the size of O(M) is used to store the ‘FREQ’ array. Hence the overall space complexity is O(2^(M*K)).

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