Most Frequent Word
You are given a paragraph that may have letters both in lowercase and uppercase, spaces, and punctuation. You have also given a list of banned words. Now your task is to find the most frequent word which is not in the list of banned words. There will always be a solution, and the solution will be unique.

While comparing words, you can ignore whether the letter is lowercase or uppercase. For example, ‘AsK’ and ‘aSK’ are the same. The words will always contain only alphabets or we can say words will be separated by spaces or punctuation. The answer will be in uppercase letters.

The words in the banned list will always be in upper letters and free from punctuation and spaces.

For example :

Paragraph = ‘It's a square SqUare. It's a FLAT flat.’ Banned =[FLAT, IT, S]. So we can see these words [IT, S, SQUARE, FLAT ] are most frequent. Now we will look at to banned list and we can see 3 of the words are banned. So we have a unique answer SQUARE which has a frequency of 2 and not on the banned list.

Input Format:

The first line of input contains a string PARAGRAPH. The second line of input contains an integer 'N' representing the size of the banned words list. The third line of input contains 'N' space-separated words BANNEDWORDS.

Output format:

Print the word (in UPPERCASE) which is most frequent and is not present in the list of banned words.

Note :

You don’t have to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1

Question

Most Frequent Word

You are given a paragraph that may have letters both in lowercase and uppercase, spaces, and punctuation. You have also given a list of banned words. Now your task is to find the most frequent word which is not in the list of banned words. There will always be a solution, and the solution will be unique.

While comparing words, you can ignore whether the letter is lowercase or uppercase. For example, ‘AsK’ and ‘aSK’ are the same. The words will always contain only alphabets or we can say words will be separated by spaces or punctuation. The answer will be in uppercase letters.

The words in the banned list will always be in upper letters and free from punctuation and spaces.

For example :

Paragraph = ‘It's a square SqUare. It's a FLAT flat.’ 
Banned =[FLAT, IT, S]. 
So we can see these words [IT, S, SQUARE, FLAT ]  are most frequent.
Now we will look at to banned list and we can see 3 of the words are banned.
So we have a unique answer SQUARE which has a frequency of 2 and not on the banned list.

Input Format:

The first line of input contains a string PARAGRAPH.
The second line of input contains an integer 'N' representing the size of the banned words list.
The third line of input contains 'N' space-separated words BANNEDWORDS.

Output format:

Print the word (in UPPERCASE) which is most frequent and is not present in the list of banned words.

Note :

You don’t have to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1<= N <=10^6
1<=banned.size<=100
Where ‘N’ is the size of paragraph.

Time limit: 1 second

Accepted Answer

Brute Force

To find the frequency of each word we need to extract the words from the paragraph.
So we will convert all the punctuation to space in the paragraph and lowercase alphabets to uppercase.
Now we can use the library function (e.g sstream in C++) to extract words from the paragraph in an array of strings say WORDS.
We will iterate over WORDS and do:
1. Iterate over the banned array and check if the current word is present in banned or not.
2. If not present in banned we will run another loop on WORDS to find its frequency.
3. If the frequency of the current word is greater than the max frequency then update the max frequency and answer(the string that function will return).
After the 4th step, we will have a word that is not banned and have the maximum frequency.

Space Complexity: O(n)Explanation:

O(N) where N is the length of the paragraph.

As we are storing the paragraph in an array of strings, which will take O(N) space.

Time Complexity: O(n^2)Explanation:

O(N^2) where N is the length of the paragraph.

As we have converted the paragraph to an array of strings. And for each word in the array we are traversing the whole array making it N^2.

Accepted Answer

Hashing

First of all, we need to extract all words into an array of strings. We can do this the same way as we did in the earlier approach. But this time we will use Hashmap to store the frequency of each word and a Set to store the banned words so that we can check if the word is banned or not in constant time.

Let's say we have given a paragraph P.
Let’s say the array of words is WORDS.
We are using an unordered_map called MYMAP as Hashmap.
We are also using a Set called MYSET to store banned words.
Let’s say MXCOUNT=0 and ANS is an empty string.
Iterate over WORDS[i] for each 0 <= i < WORDS.size() and do:
1. If WORDS[i] is present in MYSET go to step 6.
2. MYMAP[ WORDS[i] ] += 1.
3. Initialize an integer variable COUNT=.MYMAP[ WORDS[i] ].
4. If COUNT > MXCOUNT then do :
  1. MXCOUNT = COUNT
  2. ANS = WORDS[i]
Return ANS.

Space Complexity: O(n)Explanation:

O(2*N+M) where N is the length of the paragraph and M is the space used by Set.

We built a hashmap to count the frequency of each unique word, whose space would be of O(N) and we have also extracted paragraph into an array of strings taking O(N) space.

Time Complexity: O(n)Explanation:

O(N) where N is the length of the paragraph.

As we traversing a string of length N.

C++ (g++ 5.4)

/*

    Time Complexity: O(N)

    Space Complexity: O(2*N+M)



    Where N is the length of paragraph;

    Where M is the space used by banned words.

*/

#include

#include

#include

#include

string mostFreq(vectorbanned,string p)

{

    //Converting punctuations into spaces and lowercase to uppercase

    for(int i=0;i    {

        if(ispunct(p[i]))

        {

            p[i]=' ';

        }

        if(isalpha(p[i]))

        {

            p[i]=toupper(p[i]);

        }

    }



    //Stroing the banned words into a set

    unordered_set ban(banned.begin(),banned.end());



    //To store the frequency of words

    unordered_map mymap;



    //Extracting the words from paragraph

    stringstream ss(p); 

    vectorwords;



    string temp;

    while(ss>>temp)

    {

        words.push_back(temp);



    }



    int mx=0; 

    string ans;



    //Finding the word with max frequency

    for(int i=0;i    {

       

        if(ban.find(words[i])!=ban.end())

        {

            continue;

        }

        mymap[words[i]]+=1;

        int count= mymap[words[i]];



        if(count>mx)

        {

            mx=count;

            ans=words[i];

        }

    }

    return ans;

}

Java (SE 1.8)

/*
    Time Complexity: O(N)
    Space Complexity: O(2*N+M)

    Where N is the length of paragraph;
    Where M is the space used by banned words.
*/

import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Solution {

	public static String mostCommonWord(String paragraph, String[] banned) {
		String normalizedStr = paragraph.replaceAll("[^a-zA-Z0-9 ]", " ").toLowerCase();
		String[] words = normalizedStr.split("\s+");

		Set bannedWords = new HashSet<>();
		for (String word : banned){
		    bannedWords.add(word.toLowerCase());
		}

		Map wordCount = new HashMap<>();
		for (String word : words) {
		    if (!bannedWords.contains(word)){
		        wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);
		    }
		}
		
		return Collections.max(wordCount.entrySet(), Map.Entry.comparingByValue()).getKey().toUpperCase();

	}

}

Accepted Answer

Improved Hashing

We can solve this problem without extracting words into extra space and without storing Banned into Set. We will only be using a Hashmap to store the frequency of words and will initialize the Banned words with a minimum value of INTEGER say INT_MIN. And from the given constraint we know once initialized with INT_MIN Banned words frequency can never reach a positive value. And the algorithm for processing words is given below:

Let's say we have given a paragraph P.
We are using an unordered_map called MYMAP as Hashmap.
Set the MYMAP value for banned words as INT_MIN.
Iterate over P[i] for each 0 <= i < N and do:
1. If P[i] is alphabet:
  1. Convert P[i] to uppercase and append to TEMP.
2. If P[i] is a space or punctuation :
  1. MYMAP[TEMP] += 1.
  2. Set TEMP=””.
Return the word with max frequency.

Space Complexity: O(n)Explanation:

O(N) where N is the length of the paragraph.

We built a hashmap to count the frequency of each unique word, whose space would be of O(N).

Time Complexity: O(n)Explanation:

O(N) where N is the length of the paragraph.

As we traversing a string of length N.

Java (SE 1.8)

/*
    Time Complexity: O(N)
    Space Complexity: O(N)

    Where N is the length of paragraph;
*/

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Solution {

	public static String mostCommonWord(String paragraph, String[] banned) {
	Set bannedWords = new HashSet<>();
        for (String word : banned){
            bannedWords.add(word.toLowerCase());
        }

        String ans = "";
        int maxCount = 0;
        Map wordCount = new HashMap<>();
        StringBuilder wordBuffer = new StringBuilder();
        char[] chars = paragraph.toCharArray();

        for (int p = 0; p < chars.length; ++p) {
            char currChar = chars[p];

            // Use the characters in a word
            if (Character.isLetter(currChar)) {
                wordBuffer.append(Character.toLowerCase(currChar));
                if (p != chars.length - 1){
                    continue;
                }
            }

            // At the end of one word or at the end of paragraph identify the maximum count while updating the wordCount table.
                
            if (wordBuffer.length() > 0) {
                String word = wordBuffer.toString();
                if (!bannedWords.contains(word)) {
                    int newCount = wordCount.getOrDefault(word, 0) + 1;
                    wordCount.put(word, newCount);
                    if (newCount > maxCount) {
                        ans = word;
                        maxCount = newCount;
                    }
                }
                // Reset the buffer for the next word
                wordBuffer = new StringBuilder();
            }
        }
        return ans.toUpperCase();
	}

}

C++ (g++ 5.4)

/*

    Time Complexity: O(N)

    Space Complexity: O(N)



    Where N is the length of paragraph;

*/

#include

#include

string mostFreq(vectorbanned,string p)

{

    //Hashmap to store frequency of words

    unordered_mapmymap;



    for(int i=0;i    {

        mymap[banned[i]]=INT_MIN;

    }



    //Exracting words and appending to mymap

    string temp="";

    for(int i=0;i    {

        if(isalpha(p[i]))//Checking if the chracter is alphabet or not

        {

            temp+=toupper(p[i]);//Converting to UpperCase and appending to temp

        }

        else if( temp.size()>0)

        {

            mymap[temp]+=1;//We will increase the frequency of temp by 1

            temp="";

        }

    }



    if(temp.size()>0)

    {

        mymap[temp]+=1;

    }



    //Finding word with maximum frequency

    string ans="";

    int mx=INT_MIN;

    for(auto &aa:mymap)

    {  

        if(aa.second>mx)

        {

            mx=aa.second;

            ans=aa.first;

        }

    }

    return ans;

}

Accepted Answer

Steps:
Normalize the Input:

Convert all the words in the paragraph to lowercase to avoid case-sensitivity issues.
Remove punctuation like commas, periods, etc., so that only the words remain.
Split the Words:

Split the paragraph into individual words based on spaces.
Ignore Banned Words:

Keep only the words that are not part of the banned list.
Count Frequency:

Count the frequency of each word that remains after filtering the banned words.
Find the Most Frequent Word:

Identify the word with the highest frequency from the list of remaining words.
Example in Python:
import re
from collections import Counter

def most_frequent_word(paragraph, banned):
    # Normalize the paragraph by making everything lowercase and replacing punctuation with spaces
    paragraph = re.sub(r'[^\w\s]', ' ', paragraph).lower()
    
    # Split the paragraph into individual words
    words = paragraph.split()

# Create a set of banned words for faster lookup
    banned_set = set(banned)

# Filter out banned words
    filtered_words = [word for word in words if word not in banned_set]

# Count the frequency of each word
    word_count = Counter(filtered_words)

# Find the word with the highest frequency
    most_common_word = word_count.most_common(1)[0][0]

return most_common_word

# Example usage:
paragraph = "Bob hit a ball, the hit BALL flew far after it was hit."
banned = ["hit"]

print(most_frequent_word(paragraph, banned))  # Output: "ball"
Explanation of Code:
Normalization:

The re.sub(r'[^\w\s]', ' ', paragraph) replaces all punctuation with spaces. \w represents word characters (letters and numbers), and \s represents space characters. The regular expression [^...] negates these, so it replaces everything that isn't a word or space with a space.
Splitting Words:

split() breaks the normalized string into individual words, using spaces as separators.
Filtering Banned Words:

We use a list comprehension to filter out any words that are present in the banned list.
Counting Words:

Counter from the collections module counts the occurrences of each word in the filtered list.
Finding the Most Frequent Word:

most_common(1) returns the most common word in the list along with its count, and we extract the word using [0][0].
Time Complexity:
O(n) where n is the number of words in the paragraph. Each step (normalizing, filtering, counting) runs in linear time, making the solution efficient.
This method works effectively to find the most frequent non-banned word in a paragraph.

While comparing words, you can ignore whether the letter is lowercase or uppercase. For example, ‘AsK’ and ‘aSK’ are the same. The words will always contain only alphabets or we can say words will be separated by spaces or punctuation. The answer will be in uppercase letters.

The words in the banned list will always be in upper letters and free from punctuation and spaces.

For example :

Input Format:

Output format:

Note :

Constraints:

Top Josh Technology Group Web Developer interview questions & answers

Popular interview questions of Web Developer