Ninja And The Game Of Words

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
13 upvotes
Asked in companies
MicrosoftHCL TechnologiesGoldman Sachs

Problem statement

Ninja and his friend playing a game in which his friend gave him a string ‘STR’ that can contain spaces and a List/Array ‘WORDS’ which is of type string containing ‘N’ strings of words. Ninja’s task is to count the occurrences of all the words in ‘STR’.

For Example:

‘STR’ = “i am a Ninja”, ‘N’ = 3 and ‘WORDS[]’ = [“Ninja”,”a”,”am”]. Then the output should be [1,1,1]. Because the occurrence of “Ninja” in ‘STR’ is 1 and the occurrence of “a” in ‘STR’ is 1.Similarly occurrence of “am” is 1.

Note:

The output should be in the same order as given in ‘WORDS’.

Can you help Ninja to generate all valid strings from ‘STR’ by minimum removals?

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer  'T' which denotes the number of test cases. 

The first line of each test case contains an integer ‘N’.

The second line contains a string ‘STR’.

The next ‘N’ lines contain a string representing words.
Output Format : 
For each test case, return the frequency of all the words given in ‘WORDS’ Array/List

Print the output for each test case in a separate line.
Note: 
You don't need to print anything; it has already been taken care of. Just implement the given function.
Constraints: 
1 <= ‘T’ <= 100
1 <= |STR| <= 4000
1<= N <= 4000
1<= |WORDS[i]| <= 4000

Where  |'STR'| denotes the length of the given string and ‘|WORDS[i]|’ denotes the length of the string word.  

Time limit: 1 sec
Sample Input 1:
2
2
Hi i am ninja and i love coding
ninja
m  
5
Hey ninja ! How are you ?
Hey  
ninja
Ninja 
How 
yo
Sample Output 1:
1 0
1 1 0 1 0

Explanation for Sample Output 1:

For the first test case : 
1. There is only one occurrence of “ninja” in ‘STR’= “Hi i am ninja and i love coding”.
2. There is no occurrence of “m” in ‘STR’ = “Hi i am ninja and i love coding”.

For the second test case:
1. There is 1 occurrence of “Hey” in given ‘STR’ = “Hey ninja ! How are you ?”
2. There is 1 occurrence of “ninja” in given ‘STR’ = “Hey ninja ! How are you ?”
3. There is 0 occurrence of “Ninja” in given ‘STR’ = “Hey ninja ! How are you ?”
4. There is 1 occurrence of “How” in given ‘STR’ = “Hey ninja ! How are you ?”
5. There are 0 occurrences of “yo” in given ‘STR’ = “Hey ninja ! How are you ?”
Sample Input 2:
2
2
the Ninja always wins the game of coding
nja 
the
3
Hey There I am enjoying algorithms
HEY
A
There
Sample Output 2:
0 2 
2 0 1

Explanation for Sample Output 2:

For the first test case : 
1. There is no occurrence of “nja” in ‘STR’= “the Ninja always wins the game of coding”.
2. There is 2 occurrences of “the” in ‘STR’ = “the Ninja always wins the game of coding”.

For the second test case:
1. There are 2 occurrences of “Hey” in given ‘STR’ = “Hey There I am enjoying algorithms”
2.There are 0 occurrences of “A” in given ‘STR’ = “Hey There I am enjoying algorithms”
3. There is 1 occurrence of “There” in given ‘STR’ = “Hey There I am enjoying algorithms”
Hint

Try to use a brute force approach in this problem

Approaches (2)
Brute Force

The idea behind this approach is to one by one check all the words in ‘WORDS’ if they are present in ‘STR’ or NOT. If present then increases the count of that word.

 

Here is the complete algorithm:

 

  • Make an array/list ‘ANSWER’ to store the count of occurrence of each word. Iterate the ‘WORDS’ and for each word ‘WORD[i]’ at index ‘i’ in the ‘WORDS’ do the following:
    • Inetialize a variabe ‘COUNT’ = 0.
    • Iterate the ‘STR’ and for each index ‘j’ do the following:
      • If the substring of length from ‘j’ to ‘j + lengthof(WORD[i])’ is equal to the ‘WORD[i]’ then increase the ‘count’ by ‘1’.
    • Insert the value of ‘COUNT’ in the ‘ANSWER’.
  • Finally, return ‘ANSWER’.
Time Complexity

O(N * |STR| * max(WORDS[i]))

 

Because in the worst case we are iterating ‘WORDS’ and for each word in the ‘WORDS’ we are iterating the ‘STR’ and to check if two strings are equal or not we are iterating through the length of the ‘WORDS[i]’

Space Complexity

O(1)

 

Because we are not using any extra space.

Code Solution
(100% EXP penalty)
Ninja And The Game Of Words
Full screen
Console