Most Common Word — String Normalization and Frequency Counting

Problem Statement#

Given a string paragraph and a string array of banned words banned, return the most frequent word that is not banned. It is guaranteed there is at least one non-banned word, and the answer is unique.

Words in paragraph are case-insensitive and the answer must be returned in lowercase.

Constraints:

• 1 <= paragraph.length <= 1000
• paragraph consists of English letters, spaces, or punctuation: ! ? ' , ; .
• 0 <= banned.length <= 100
• 1 <= banned[i].length <= 10
• banned[i] consists of only lowercase English letters

Input:  paragraph = "Bob hit a ball, the hit BALL flew far after it was hit."
        banned = ["hit"]
Output: "ball"
Explanation: "hit" appears 3 times but is banned. "ball" appears 2 times — the most frequent non-banned word.

Input:  paragraph = "Bob. hIt, baLl"
        banned = ["bob", "hit"]
Output: "ball"

Why This Problem Matters#

Most Common Word (LC 819) is deceptively simple yet encapsulates several practical skills that appear in real-world text processing and data engineering roles. Amazon and Microsoft use it in screens because it tests: input normalisation, tokenisation using regex or manual parsing, set lookup for banned words, and frequency counting with a hash map.

The real-world analogue is immediately obvious: search engines compute term frequency while filtering stop words; ad targeting systems find the most common topics in a corpus; content moderation pipelines normalise and tokenise text before applying blocklists. Candidates who frame their solution in these terms show applied thinking beyond just solving the puzzle.

The problem also has a subtle implementation trap: candidates who iterate character-by-character to extract words write far more code — and make more mistakes — than those who use re.findall(r'[a-z]+', paragraph.lower()). Interviewers at Amazon specifically value candidates who reach for the right standard-library tool.

The Core Insight#

Three steps solve this problem cleanly:

1. Normalise: Convert the entire paragraph to lowercase. This handles "Bob" vs "bob" vs "BOB".
2. Tokenise: Extract words by stripping all punctuation. Regex [a-z]+ matches one or more lowercase letters — any contiguous letter sequence is a word, regardless of surrounding punctuation.
3. Filter and count: Build a frequency map for words not in the banned set. Return the word with the highest frequency.

Converting banned to a set before lookup is important. Checking word in banned_set is O(1), while word in banned_list is O(b). The habit of set conversion for membership testing is critical in larger-scale problems even if it makes little difference at this input size.

Visual Dry Run#

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

Step 1 — Lowercase: "bob hit a ball, the hit ball flew far after it was hit."

Step 2 — Tokenise with regex: ["bob","hit","a","ball","the","hit","ball","flew","far","after","it","was","hit"]

Step 3 — Frequency map (skipping banned):

Maximum: "ball" with count 2. Answer: "ball".

Solution (Optimal)#

import re
from collections import Counter
 
def mostCommonWord(paragraph: str, banned: list[str]) -> str:
    banned_set = set(banned)
 
    # Lowercase and extract letter sequences only
    words = re.findall(r'[a-z]+', paragraph.lower())
 
    # Count non-banned words
    freq = Counter(word for word in words if word not in banned_set)
 
    return freq.most_common(1)[0][0]

var mostCommonWord = function(paragraph, banned) {
    const bannedSet = new Set(banned);
 
    // Lowercase and extract letter-only tokens
    const words = paragraph.toLowerCase().match(/[a-z]+/g) || [];
 
    const freq = new Map();
    for (const word of words) {
        if (!bannedSet.has(word)) {
            freq.set(word, (freq.get(word) || 0) + 1);
        }
    }
 
    let bestWord = '';
    let bestCount = 0;
    for (const [word, count] of freq) {
        if (count > bestCount) {
            bestCount = count;
            bestWord = word;
        }
    }
 
    return bestWord;
};

Time: O(n + b) where n = paragraph length and b = banned list length. Space: O(n + b) — frequency map plus banned set.

Common Mistakes#

• Not converting to lowercase before tokenising: "Ball" and "ball" would be counted separately.
• Using split() without stripping punctuation: "ball,".split() gives ["ball,"] — the comma stays attached. Use regex.
• Checking word in banned (list) instead of a set: O(b) per lookup vs O(1). Build the set once at the start.
• Forgetting that r'[a-z]+' only matches lowercase: The paragraph must be lowercased first or the pattern changed to r'[a-zA-Z]+'.
• Apostrophes in contractions: "don't" splits into "don" and "t" with this regex. For most interview versions this is acceptable — mention it as a limitation.

Interview Tips#

• State the three-step plan before writing any code: normalise, tokenise, count.
• Explain why set(banned) before the loop is important even if not needed at this scale.
• Point out that re.findall handles all punctuation edge cases in one line.
• If asked about scaling: "For 10 GB text, stream line by line and accumulate a bounded Counter."

Follow-up Questions#

• What if you need the top-k most common non-banned words? Use Counter.most_common(k) or a min-heap of size k.
• How would you handle contractions like "don't" as a single word? Adjust the regex to allow internal apostrophes: r"[a-z']+".
• How would you implement this in a distributed system? Map phase emits (word, 1) for each non-banned word; reduce phase sums counts per word; a final global reduce finds the maximum.
• What if banned words could be multi-word phrases? Tokenise, then use a sliding window to check multi-word sequences against a phrase set.
• How does this relate to TF-IDF? Term frequency is the raw count computed here; TF-IDF normalises it by how common the word is across all documents to penalise stop words.

Key Takeaways#

• Most Common Word (LC 819) tests normalisation, tokenisation, set membership, and frequency counting — four foundational string-processing skills.
• Lowercase the paragraph before applying a lowercase-only regex pattern.
• re.findall(r'[a-z]+', text) extracts words while automatically stripping all punctuation.
• Convert banned to a set for O(1) membership checks; never iterate a list for membership.
• Time O(n + b), space O(n + b) — linear in input size.
• The three-step plan (normalise → tokenise → filter and count) applies to virtually any text frequency problem.
• For FAANG interviews, frame the solution in terms of real-world analogues: search engine stop-word filtering, content moderation pipelines.