Most Frequent Word

Easy
0/40
Average time to solve is 15m
profile
Contributed by
10 upvotes
Asked in companies
McAfeeAdobeCognizant

Problem statement

You are given two strings 'A' and 'B' of words. Your task is to find out the most frequent and lexicographically smallest word in string 'A', which is not present in string 'B'. If no such word is present in 'A', then return -1.

Note:

1. A word is a sequence of one or more lowercase characters.

2. Words are separated by a single whitespace character.
Example: 
For the given string 'A' = “coding ninjas coding ninjas” and 'B' = “data structures and algorithms”, so both the word 'coding' and 'ninjas' are not present in string 'B' and occur two times each, but the word “coding” is lexicographically smaller than the word “ninjas”. So the answer is “coding”.
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line contains an integer 'T' which denotes the number of test cases. 

The first line of each test case contains a string 'A', having lowercase English letters only.

The second line of each test case contains a string 'B', having lowercase English letters only.
Output format: 
For each test case, return the most frequent and lexicographically smallest word in string 'A', which is not present in string B. If no such word exists, return -1.
Note: 
You don't need to print anything, It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= |A|, |B| <= 10^5 

Where |A|, |B| denotes the length of string 'A' and 'B' respectively.   

Time limit: 1 sec
Sample Input 1:
2
yuvraj hit six sixes in six balls
yuvraj is a cricketer
coding ninjas coding ninjas
computer science
Sample Output 1:
six
coding
Explanation for Sample Output 1:
In test case 1, “six” is the only word which occurs the most number of times in string 'A' and is not present in string 'B'.

In test case 2, both the word “coding” and “ninjas” occur two times in string 'A' and is not present in string 'B'. Since, the word “coding” is lexicographically smaller than “ninjas”, hence we return “coding”.
Sample Input 2:
2
a a b b c c d
a b d
this algorithm repeats the same process again and again
this algorithm repeats the same process again and again
Sample Output 2:
c
-1
Explanation for Sample Output 2:
In test case 1, the words “a”, “b” and “c” occur 3 times in string 'A', but “a” and “b” are present in 'B'. Hence, we return “c”.

In test case 2, both the strings are equal. Hence we return an -1 as there is no such word which is present in 'A', but not present in 'B'.
Hint

Think of brute force to check for each word in A, which is not present in B and count its occurrence.

Approaches (2)
Brute-force

If the string 'A' is empty or both the strings are equal, then we simply return “-1”. We initially initialise an empty string say 'ANS', which is the final string to be returned as the answer and a 'MAX' variable to 0, which will be used to store the occurrence of 'ANS' in the string 'A'.


We initially initialise an empty string say ‘TEMP’ and a ‘COUNT’ variable to 1. Then, we will traverse the input string 'A' from left to right and keep on adding the current character to the ‘TEMP’ string until we encounter a space. As soon as we encounter a space, we check whether the temp string is present in the string 'B' or not. If it is present in the string 'B', then we make the temp string empty again and traverse the remaining part of string 'A'.


If it is not present in the string 'B', then we check for its occurrence in the remaining part of string 'A' and increase the count variable by 1, each time we encounter the ‘TEMP’ string.


If the value of count is greater than the 'MAX' variable, then update the value of 'ANS' as the ‘TEMP’ and make 'MAX' variable equal to count. Else if the value of count is equal to 'MAX' and ‘TEMP’ string is lexicographically smaller than 'ANS', then also update the value of 'ANS' as the 'TEMP'.


Finally, if 'ANS' string is empty, we simply return “-1”, else return the 'ANS' string.

Time Complexity

O((N ^ 2) * M), Where ‘N’ and ‘M’ are the lengths of the string ‘A’ and ‘B’ respectively.

 

Since we will be traversing the whole string A, which takes O(N) time, and for each word, we check for its existence in string B, which takes O(M) time. If it is not present in B, then we count its occurrence in the remaining string of A which takes O(N) time again. So in the worst case, when all the words of the string A are unique, for each word, we need to traverse the whole string A and B. Hence, the time complexity will be O((N ^ 2) * M).

Space Complexity

O(1).

 

Since constant space is required, hence the space complexity will be O(1).

Code Solution
(100% EXP penalty)
Most Frequent Word
Full screen
Console