Get started

Most Common Word — Easy Problem & Solution

Given a paragraph and a list of banned words, return the most frequent word that is not banned.

  • Difficulty: Easy
  • Topics: Strings, Hash Table
  • Asked at: Amazon, Adobe, Infosys
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given a paragraph and a list of banned words, return the most frequent word that is not banned.

Words are case-insensitive and the answer is returned in lowercase. Anything that is not a letter separates words. The answer is unique; when several words tie, the one that reaches the winning count first wins.

Example 1

Input: paragraph = "CodeKairo drills, codekairo rounds, codekairo wins!", banned = ["rounds"]
Output: codekairo
Explanation: codekairo appears three times and is not banned.

Example 2

Input: paragraph = "Bob hit a ball, the hit BALL flew far after it was hit.", banned = ["hit"]
Output: ball
Explanation: hit is banned, so ball with two occurrences wins.

Example 3

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

Constraints

  • 1 <= paragraph.length <= 1000
  • 0 <= banned.length <= 100
  • paragraph holds English letters, spaces and the punctuation !?',;.
  • banned words are lowercase and letters only.

How to solve Most Common Word

Tokenise by scanning for maximal runs of letters, lowercase each token, skip the banned ones and count the rest — keeping the running maximum as you go.

Approach

  1. Put the banned words into a set, lowercased.
  2. Sweep the paragraph accumulating letters into a buffer; any non-letter flushes the buffer as one word.
  3. Lowercase the flushed word, skip it if banned, otherwise increment its count.
  4. Whenever a count strictly exceeds the best so far, adopt that word as the answer.
  5. Flush once more after the loop so a paragraph ending in a letter is not dropped.

Why it works

Updating the best on a strict > means the first word to reach a given count keeps the title, which is the tie-break the statement describes. Scanning character by character avoids having to enumerate every punctuation mark.

Complexity

  • Time — O(n + b)
  • Space — O(n + b)

Pitfalls

  • Splitting on spaces alone leaves punctuation stuck to words, so "ball," and "ball" count separately.
  • Forgetting the final flush loses the last word when the paragraph does not end in punctuation.
  • Comparing against the banned list case-sensitively misses capitalised occurrences.

Reference solution

Python

from typing import List

def mostCommonWord(paragraph: str, banned: List[str]) -> str:
    block = set(b.lower() for b in banned)
    count = {}
    best, best_n = "", 0
    cur = []
    def flush():
        nonlocal best, best_n, cur
        if not cur:
            return
        w = "".join(cur).lower()
        cur = []
        if w in block:
            return
        count[w] = count.get(w, 0) + 1
        if count[w] > best_n:
            best_n = count[w]
            best = w
    for c in paragraph:
        if c.isalpha():
            cur.append(c)
        else:
            flush()
    flush()
    return best

JavaScript

var mostCommonWord = function(paragraph, banned) {
    var block = {};
    for (var b = 0; b < banned.length; b++) block[banned[b].toLowerCase()] = true;
    var count = {}, best = "", bestN = 0, cur = "";
    var flush = function() {
        if (cur.length === 0) return;
        var w = cur.toLowerCase();
        cur = "";
        if (block[w] === true) return;
        count[w] = (count[w] === undefined ? 0 : count[w]) + 1;
        if (count[w] > bestN) { bestN = count[w]; best = w; }
    };
    for (var i = 0; i < paragraph.length; i++) {
        var c = paragraph.charAt(i);
        if ((c >= "a" && c <= "z") || (c >= "A" && c <= "Z")) cur += c;
        else flush();
    }
    flush();
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue