Domain 1EasyCORE

Most Common Word

The problem requires finding the most frequent non-banned word in a given paragraph. The words are case-insensitive, and punctuation should be ignored. The input consists of a string `paragraph` and an array of banned words `banned`. The output is the most frequent non-banned word in lowercase.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#String

819. Most Common Word

Model: qwen2.5-coder:14b
Topics: String
FAANG asked: 1
Acceptance rate: 45.5%


Problem Breakdown

The problem requires finding the most frequent non-banned word in a given paragraph. The words are case-insensitive, and punctuation should be ignored. The input consists of a string paragraph and an array of banned words banned. The output is the most frequent non-banned word in lowercase.

Inputs:

  • paragraph: A string containing English letters, spaces, or punctuation.
  • banned: An array of strings representing banned words.

Outputs:

  • A single string representing the most frequent non-banned word in lowercase.

Implicit Constraints/Edge Cases:

  • The paragraph can contain punctuation adjacent to words.
  • Words are case-insensitive.
  • There is at least one non-banned word in the paragraph.
  • The answer is guaranteed to be unique.

Intuition

A brute-force approach would involve:

  1. Splitting the paragraph into words while ignoring punctuation and converting them to lowercase.
  2. Counting the occurrences of each word, excluding banned words.
  3. Finding the word with the highest count.

This approach is inefficient because it involves multiple passes over the data and uses additional space for storing counts.

A better approach leverages a hash map (dictionary) to efficiently count word occurrences and another set for banned words. This reduces time complexity by allowing constant-time lookups for both counting and checking bans.

Approach

  1. Normalize the Paragraph: Convert the paragraph to lowercase and replace all punctuation with spaces.
  2. Split into Words: Use the split() method to break the paragraph into individual words.
  3. Count Non-Banned Words: Use a dictionary to count occurrences of each word that is not in the banned list.
  4. Find the Most Frequent Word: Iterate through the dictionary to find the word with the highest count.

Data Structures:

  • Dictionary: To store word counts.
  • Set: To store banned words for O(1) lookup time.

Complexity Analysis

  • Time Complexity: O(n + m), where n is the length of the paragraph and m is the number of banned words. This accounts for splitting the paragraph, counting words, and finding the most frequent word.
  • Space Complexity: O(n + m), for storing the dictionary of word counts and the set of banned words.

Solution

def mostCommonWord(paragraph: str, banned: List[str]) -> str:
    # Normalize the paragraph by converting to lowercase and replacing punctuation with spaces
    normalized_paragraph = ''.join([char.lower() if char.isalnum() else ' ' for char in paragraph])
    
    # Split the paragraph into words
    words = normalized_paragraph.split()
    
    # Create a set of banned words for O(1) lookup time
    banned_set = set(banned)
    
    # Dictionary to store word counts
    word_count = {}
    
    # Count occurrences of each non-banned word
    for word in words:
        if word not in banned_set:
            if word in word_count:
                word_count[word] += 1
            else:
                word_count[word] = 1
    
    # Find the most frequent non-banned word
    most_frequent_word = max(word_count, key=word_count.get)
    
    return most_frequent_word

Edge Cases Handled

  • Punctuation Adjacent to Words: Replacing punctuation with spaces ensures words are correctly identified.
  • Case Insensitivity: Converting the paragraph to lowercase handles case insensitivity.
  • Empty Banned List: The code works correctly even if no words are banned.
  • Unique Answer: The problem guarantees a unique answer, so the code does not need to handle ties.