Most Frequent Word

Posted: 19 Dec, 2020
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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”.
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
Approach 1

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.

Try Problem