Ninja And The Game Of Words
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,3,1]. Because the occurrence of “Ninja” in ‘STR’ is 1 and the occurrence of “a” in ‘STR’ is 3.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?

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

Question

Ninja And The Game Of Words

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,3,1]. Because the occurrence of “Ninja” in ‘STR’ is 1 and the occurrence of “a” in ‘STR’ is 3.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?

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

Accepted Answer

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’.

Space Complexity: O(1)Explanation:

O(1)

Because we are not using any extra space.

Time Complexity: OtherExplanation:

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]’

Java (SE 1.8)

/*

	Time complexity: O(N * |STR| * max('WORDS'[i]))

	Space complexity: O(1)



	Where 'N' is the number of elements in 'WORDS', |STR| length of 'STR'.

*/



import java.util.ArrayList;



public class Solution {

	public static ArrayList getFrequency(String str, ArrayList words, int n) {

		String[] strArr = str.split(" ");

		

		// Splitting 'STR' by spaces and storing in vector.

		ArrayList answer = new ArrayList<>(n);

		for (String word : words) {

			int count = 0;

			for (String strWord : strArr) {

				if (strWord.equals(word)) {

					count++;

				}

			}

			answer.add(count);



		}



		return answer;

	}

}

C++ (g++ 5.4)

/*

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

	Space complexity: O(1)



	Where 'N' is the number of elements in 'WORDS', |STR| length of 'STR'.

*/



#include 



vector getFrequency(string& str, vector& words, int n) {



	vector strArr;

	// Splitting 'STR' by spaces and storing in vector.

	istringstream iss(str);

	for(string s; iss >> s;) {

		strArr.push_back(s);

	}



	vector answer;

	for (string word : words) {

		int count = 0;

		for (string strWord : strArr) {

			if (strWord == word) {

				count++;

			}

		}

		answer.push_back(count);



	}



	return answer;

}

Python (3.5)

"""

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

	Space complexity: O(1)



	Where 'N' is the number of elements in 'WORDS', |STR| length of 'STR'.

"""



def getFrequency(str, words, n):

	strArr = []

	# Splitting 'STR' by spaces and storing in vector.

	x = len(str)

	s = ""

	for i in range(x): 

		if(str[i] == ' '):

			strArr.append(s)

			s=""

		else:

			s += str[i]

	strArr.append(s)

	

	answer = []

	for word in words:

		count = 0

		for strWord in strArr:

			if (strWord == word): 

				count += 1

			

		answer.append(count)



	return answer

Accepted Answer

Hashing

The idea behind this approach is to store all the words in the ‘STR’ in a map with its frequency and then traverse ‘WORDS’ and for each word in ‘WORDS’ get the frequency from the map.

Here is the complete algorithm:

Make a hash map ‘MP’ of type ‘MP’ and an array/list ‘ANSWER’ to store the frequency of all the words in the ‘WORDS’.
Iterate the ‘STR’ and extract the words one by one and for each word insert this word in the ‘MP’. There are two following cases:
- If the word is already present in the ‘MP’ then simply increase its count.
- Else insert the word with frequency ‘1’.
Iterate the ‘WORDS’ and for each ‘WORD[i]’ in the ‘WORDS’ does the following:
- Get the frequency of ‘WORDS[i]’ and insert it in the answer.

Finally, return the ‘ANSWER’.

Space Complexity: OtherExplanation:

O(|STR|) where |STR| denotes the length of the given string.

Because in the worst case all the elements in the |STR| will be inserted into the map. Hence overall space complexity will be |STR|.

Time Complexity: OtherExplanation:

O(max(N, |STR|)), where N denotes the number of words in the List/Array ‘WORDS’ and |STR| denotes the length of the given string.

Because in the worst case we iterate the |STR| and insert the words in ‘STR’ into the map and then iterating the ‘WORDS’ so overall time complexity will be the maximum of these two. Hence overall time complexity will be O(max(N, STR)).

Python (3.5)

"""

	Time complexity: O(max(|STR|, N))

	Space complexity: O(|STR|)



	Where 'N' is the number of elements in words, |STR| length of 'STR'.

"""



def getFrequency(str, words, n):

	strArr = []

	# Splitting 'STR' by spaces and storing in vector.

	x = len(str)

	s = ""

	for i in range(x): 

		if(str[i] == ' '):

			strArr.append(s)

			s=""

		else:

			s += str[i]

	strArr.append(s)



	answer = []

	mp = {}



	for strWord in strArr:

		if(strWord not in mp.keys()):

			mp[strWord] = 0



		mp[strWord] += 1



	for word in words:

		if word not in mp.keys():

			answer.append(0)

		else:

			answer.append(mp[word])



	return answer

Java (SE 1.8)

/*

	Time complexity: O(max(|STR|, N))

	Space complexity: O(|STR|)



	Where 'N' is the number of elements in words, |STR| length of 'STR'.

*/



import java.util.ArrayList;

import java.util.HashMap;



public class Solution {

	public static ArrayList getFrequency(String str, ArrayList words, int n) {

		String[] strArr = str.split(" ");

		

		// Splitting 'STR' by spaces and storing in vector.

		ArrayList answer = new ArrayList<>(n);

		HashMap mp = new HashMap<>();



		for (String strWord : strArr) {

			if (!mp.containsKey(strWord)) {

				mp.put(strWord, 1);

			} else {

				mp.put(strWord, mp.get(strWord) + 1);

			}



		}



		for (String word : words) {

			if (mp.containsKey(word)) {

				answer.add(mp.get(word));

			} else {

				answer.add(0);

			}

		}



		return answer;

	}

}

C++ (g++ 5.4)

/*

	Time complexity: O(max(|STR|, N))

	Space complexity: O(|STR|)



	Where 'N' is the number of elements in words, |STR| length of 'STR'.

*/



#include 

#include 



vector getFrequency(string& str, vector& words, int n) {



	vector strArr;



	// Splitting 'STR' by spaces and storing in vector.

	istringstream iss(str);

	for(string s; iss >> s;) {

		strArr.push_back(s);

	}



	vector answer;

	unordered_map mp;



	for (string strWord : strArr) {

		mp[strWord]++;

	}



	for (string word : words) {

		if (mp.find(word) != mp.end()) {

			answer.push_back(mp[word]);

		} else {

			answer.push_back(0);

		}

	}



	return answer;

}

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:

Note:

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

Input Format:

Output Format :

Note:

Constraints:

Top Goldman Sachs Analyst interview questions & answers

Popular interview questions of Analyst

Top HR questions asked in Goldman Sachs Analyst