Most Common Word

Difficulty: Easy | Acceptance: 45.10% | Paid: No Topics: Array, Hash Table, String, Counting

Given a string paragraph and a string array banned, return the most frequent word that is not banned. It is guaranteed there is at least one answer. Words in the paragraph are case-insensitive and the answer should be returned in lowercase.

A word is defined as:

• A maximal sequence of characters consisting of non-space characters only.

• The characters can include letters, digits, or punctuation symbols like ”!?’,;.“.

• Some words may contain punctuation symbols attached to them.

• Examples

• Constraints

• Approach 1: Hash Map with String Processing

• Approach 2: Regular Expression

• Approach 3: Two Pass with Set

Examples

Example 1:

Input: paragraph = "Bob hit a ball, the hit BALL flew far after it was hit.", banned = ["hit"]
Output: "ball"
Explanation: "hit" occurs 3 times, but it is a banned word. "ball" occurs twice (and is not banned). No other word occurs more than once.

Example 2:

Input: paragraph = "a.", banned = []
Output: "a"

Constraints

1 <= paragraph.length <= 1000
paragraph consists of English letters, space ' ', or one of the symbols: "!?',;."
0 <= banned.length <= 100
banned[i] consists of only lowercase English letters.

Approach 1: Hash Map with String Processing

Intuition Parse the paragraph character by character, building words by accumulating letters while ignoring punctuation. Use a hash map to count word frequencies and skip banned words.

Steps

• Convert banned array to a set for O(1) lookup
• Iterate through each character in the paragraph
• Build words by accumulating lowercase letters
• When a non-letter is encountered, process the completed word
• Count frequencies using a hash map, skipping banned words
• Find and return the word with maximum frequency

class Solution:
    def mostCommonWord(self, paragraph: str, banned: list[str]) -> str:
        banned_set = set(banned)
        word_count = {}
        word = []
        
        for char in paragraph + ' ':
            if char.isalpha():
                word.append(char.lower())
            else:
                if word:
                    w = ''.join(word)
                    if w not in banned_set:
                        word_count[w] = word_count.get(w, 0) + 1
                    word = []
        
        max_count = 0
        result = ""
        for w, count in word_count.items():
            if count > max_count:
                max_count = count
                result = w
        
        return result

Complexity

• Time: O(n + m) where n is paragraph length and m is total banned words length
• Space: O(n) for the hash map storing word counts
• Notes: Single pass through paragraph with efficient set lookup for banned words

Approach 2: Regular Expression

Intuition Use regular expressions to extract all words from the paragraph in one operation, then count frequencies while filtering out banned words.

Steps

• Convert banned array to a set for O(1) lookup
• Use regex to find all word sequences in the paragraph
• Convert all words to lowercase
• Count frequencies using a hash map, skipping banned words
• Find and return the word with maximum frequency

import re
from collections import Counter

class Solution:
    def mostCommonWord(self, paragraph: str, banned: list[str]) -> str:
        banned_set = set(banned)
        words = re.findall(r'\w+', paragraph.lower())
        
        word_count = Counter()
        for word in words:
            if word not in banned_set:
                word_count[word] += 1
        
        return word_count.most_common(1)[0][0]

Complexity

• Time: O(n + m) where n is paragraph length and m is total banned words length
• Space: O(n) for the hash map storing word counts
• Notes: Cleaner code with regex but may have slightly higher constant overhead

Approach 3: Two Pass with Set

Intuition Separate the counting and filtering phases: first count all word frequencies, then find the most frequent word that is not banned.

Steps

• Convert banned array to a set for O(1) lookup
• First pass: extract all words and count their frequencies
• Second pass: iterate through counted words and find the most frequent non-banned word
• Return the result

class Solution:
    def mostCommonWord(self, paragraph: str, banned: list[str]) -> str:
        banned_set = set(banned)
        word_count = {}
        
        # First pass: extract and count words
        word = []
        for char in paragraph + ' ':
            if char.isalpha():
                word.append(char.lower())
            else:
                if word:
                    w = ''.join(word)
                    word_count[w] = word_count.get(w, 0) + 1
                    word = []
        
        # Second pass: find most frequent non-banned word
        max_count = 0
        result = ""
        for w, count in word_count.items():
            if w not in banned_set and count > max_count:
                max_count = count
                result = w
        
        return result

Complexity

• Time: O(n + m) where n is paragraph length and m is total banned words length
• Space: O(n) for the hash map storing word counts
• Notes: Clear separation of concerns but requires storing all word counts including banned ones