Most Frequent Non-Banned Word Problem Statement

Given a paragraph consisting of letters in both lowercase and uppercase, spaces, and punctuation, along with a list of banned words, your task is to find the most frequent word that is not in the list of banned words. The solution will always exist and be unique.

While considering words, treat letters as case-insensitive (e.g., 'AsK' and 'aSK' are the same). Words consist solely of alphabets, separated by spaces or punctuation, and the result should be returned in uppercase.

Example:

Input:

Paragraph = "It's a square SqUare. It's a FLAT flat."
N = 3
BANNEDWORDS = [ "FLAT", "IT", "S" ]

Output:

SQUARE

Explanation:

The most frequent words (case-insensitive) are [IT, S, SQUARE, FLAT], each appearing twice. After checking with the banned list, 'SQUARE' remains as the most frequent word not banned, with a frequency of 2.

Constraints:

1

Question

Most Frequent Non-Banned Word Problem Statement

Given a paragraph consisting of letters in both lowercase and uppercase, spaces, and punctuation, along with a list of banned words, your task is to find the most frequent word that is not in the list of banned words. The solution will always exist and be unique.

While considering words, treat letters as case-insensitive (e.g., 'AsK' and 'aSK' are the same). Words consist solely of alphabets, separated by spaces or punctuation, and the result should be returned in uppercase.

Example:

Input:

Paragraph = "It's a square SqUare. It's a FLAT flat."
N = 3 
BANNEDWORDS = [ "FLAT", "IT", "S" ]

Output:

SQUARE

Explanation:

The most frequent words (case-insensitive) are [IT, S, SQUARE, FLAT], each appearing twice. After checking with the banned list, 'SQUARE' remains as the most frequent word not banned, with a frequency of 2.

Constraints:

1 <= N <= 10⁶ (where N is the size of the paragraph)
1 <= banned.size <= 100
Time limit: 1 second

Note:

You do not need to output anything as it's handled elsewhere. Your task is to implement the given function.

Accepted Answer

Find the most frequent word in a paragraph that is not in a list of banned words.

Split the paragraph into words and convert them to uppercase for case-insensitivity.
Count the frequency of each word, excluding banned words.
Return the word with the highest frequency in uppercase.

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.