Problem Description

You are given a paragraph of text and a list of banned words. Your task is to find the most frequently occurring word in the paragraph that is not in the banned list.

The problem has the following requirements and guarantees:

1. Case-insensitive matching: Words in the paragraph should be treated as case-insensitive (e.g., "Bob" and "bob" are the same word)
2. Return lowercase: The answer should be returned in lowercase
3. Ignore punctuation: Words in the paragraph may be separated by punctuation symbols, which should be ignored when extracting words
4. Unique answer: It's guaranteed that there will be exactly one most frequent non-banned word
5. At least one valid word: There will always be at least one word that isn't banned

For example, if the paragraph is "Bob hit a ball, the hit BALL flew far after it was hit." and banned words are ["hit"], then:

• Extract words: ["bob", "hit", "a", "ball", "the", "hit", "ball", "flew", "far", "after", "it", "was", "hit"]
• Count frequencies excluding banned words: "ball" appears 2 times, "bob" appears 1 time, etc.
• Return "ball" as it's the most frequent non-banned word

Intuition

The key insight is that we need to perform three main operations: extract valid words from the paragraph, count their frequencies, and filter out banned words.

First, we need to handle the text preprocessing. Since punctuation separates words and we need case-insensitive comparison, we can convert the entire paragraph to lowercase and extract only alphabetic sequences. Using a regular expression pattern [a-z]+ on the lowercased text elegantly solves both problems at once - it automatically skips punctuation and gives us clean words.

For the banned words, we can optimize lookups by converting the list into a set. Checking if a word is banned becomes an O(1) operation instead of O(n) for each word we examine.

To count word frequencies, we can use a Counter (or hashmap) to track how many times each word appears. This gives us the frequency data we need to identify the most common words.

The final step is finding the most frequent non-banned word. Instead of manually sorting and filtering, we can leverage the Counter's most_common() method which returns words ordered by frequency (highest first). We then iterate through this sorted list and return the first word that isn't in our banned set.

The elegance of this approach is that by using next() with a generator expression on the sorted frequency list, we automatically get the first (most frequent) word that passes our filter condition, which is guaranteed to exist per the problem constraints.

Solution Approach

The implementation uses a combination of regular expressions, set operations, and Python's Counter class to efficiently solve the problem.

Step 1: Convert banned list to a set

s = set(banned)

We convert the banned list into a set for O(1) lookup time when checking if a word is banned.

Step 2: Extract and count words

p = Counter(re.findall('[a-z]+', paragraph.lower()))

This line does multiple things:

• paragraph.lower() converts the entire paragraph to lowercase
• re.findall('[a-z]+', ...) uses regex to find all sequences of lowercase letters, effectively:
  • Splitting the text by any non-letter characters (punctuation, spaces, etc.)
  • Extracting only valid words as continuous letter sequences
• Counter(...) creates a frequency map of all extracted words

The regex pattern [a-z]+ matches one or more consecutive lowercase letters, which perfectly handles punctuation separation. For example, "Bob's ball." becomes ["bob", "s", "ball"].

Step 3: Find the most common non-banned word

return next(word for word, _ in p.most_common() if word not in s)

This line:

• p.most_common() returns a list of (word, count) tuples sorted by frequency in descending order
• The generator expression (word for word, _ in ... if word not in s) iterates through the sorted list and yields only words that aren't in the banned set
• next() returns the first word from this generator, which is guaranteed to be the most frequent non-banned word

The underscore _ is used as a placeholder since we don't need the count value, only the word itself.

Time Complexity: O(n + m) where n is the length of the paragraph and m is the number of unique words Space Complexity: O(m) for storing the word frequencies and banned set

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Input:

• paragraph = "Apple, apple pie; APPLE juice!"
• banned = ["pie"]

Step 1: Convert banned list to set

s = set(["pie"])  # s = {"pie"}

This gives us O(1) lookup for checking banned words.

Step 2: Extract and count words

First, convert to lowercase:

"Apple, apple pie; APPLE juice!" → "apple, apple pie; apple juice!"

Then apply regex [a-z]+ to find all letter sequences:

re.findall('[a-z]+', "apple, apple pie; apple juice!")
→ ["apple", "apple", "pie", "apple", "juice"]

Create frequency counter:

Counter(["apple", "apple", "pie", "apple", "juice"])
→ {"apple": 3, "pie": 1, "juice": 1}

Step 3: Find most common non-banned word

Get words sorted by frequency:

p.most_common() → [("apple", 3), ("pie", 1), ("juice", 1)]

Iterate through and filter banned words:

• Check "apple": not in {"pie"} ✓ → Return "apple"

Result: "apple" (appears 3 times, most frequent non-banned word)

The solution efficiently handles punctuation, case-insensitivity, and banned word filtering in just a few lines of code.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n + m + k log k)

• O(n) for converting the paragraph to lowercase where n is the length of the paragraph
• O(n) for the regex findall operation to extract all words
• O(m) for creating the banned words set where m is the number of banned words
• O(k) for creating the Counter where k is the number of unique words found
• O(k log k) for most_common() which internally sorts the words by frequency
• O(k) in the worst case for iterating through sorted words to find the first non-banned word
• Overall: O(n + m + k log k) where typically k << n

Space Complexity: O(n + m + k)

• O(m) for storing the banned words set
• O(n) for storing the lowercase paragraph temporarily
• O(n) for storing the list of words extracted by regex
• O(k) for the Counter dictionary storing unique words and their frequencies
• Overall: O(n + m + k) where n is the paragraph length, m is the number of banned words, and k is the number of unique words

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Word Extraction with Special Characters

A common mistake is trying to split words using simple string operations like split() or split(' '), which fails to handle punctuation correctly.

Incorrect approach:

words = paragraph.lower().split()  # Won't handle punctuation
# "Bob's" remains as "bob's" instead of separating to "bob" and "s"

Why it fails: Words like "Bob's", "hit.", or "ball," would be treated as single tokens including the punctuation, leading to incorrect word counting.

Solution: Use regex pattern [a-z]+ to extract only letter sequences:

words = re.findall(r'[a-z]+', paragraph.lower())

2. Case Sensitivity Issues

Forgetting to normalize the case can lead to treating "Bob" and "bob" as different words.

Incorrect approach:

word_counts = Counter(re.findall(r'[a-zA-Z]+', paragraph))  # Mixed case
# "Bob" and "bob" counted separately

Solution: Always convert to lowercase before processing:

word_counts = Counter(re.findall(r'[a-z]+', paragraph.lower()))

3. Using List Instead of Set for Banned Words

Checking membership in a list is O(n) per lookup, which can significantly slow down the solution for large banned lists.

Inefficient approach:

for word, count in word_counts.most_common():
    if word not in banned:  # O(n) lookup if banned is a list
        return word

Solution: Convert banned list to set for O(1) lookups:

banned_words = set(banned)
if word not in banned_words:  # O(1) lookup

4. Manual Frequency Tracking Instead of Using Counter

Attempting to manually track the maximum frequency while iterating can lead to complex and error-prone code.

Error-prone approach:

max_count = 0
result = ""
for word in words:
    if word not in banned:
        count = words.count(word)  # Inefficient O(n) operation
        if count > max_count:
            max_count = count
            result = word

Solution: Use Counter's most_common() method which handles sorting by frequency automatically:

word_counts = Counter(words)
for word, _ in word_counts.most_common():
    if word not in banned_words:
        return word