Most Common Word

Easy
634.

Most Common Word

Most Common Word is an easy coding problem on strings and hash table, asked in Amazon, Adobe and Infosys interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} paragraph
 * @param {string[]} banned
 * @return {string}
 */
var mostCommonWord = function(paragraph, banned) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Most Common Word — Solution in Python, Java & C++

Most Common Word solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Most Common Word is an easy coding problem on strings and hash table, asked in Amazon, Adobe and Infosys interviews.

  • 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.

Hints for Most Common Word

  1. Hint 1

    Normalise first: lowercase everything and treat every non-letter as a separator.

  2. Hint 2

    A set of banned words makes the exclusion a single lookup.

  3. Hint 3

    Track the running best while counting so no second pass over the map is needed.

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

Java

public static String mostCommonWord(String paragraph, String[] banned) {
    Set<String> block = new HashSet<>();
    for (String b : banned) block.add(b.toLowerCase());
    Map<String, Integer> count = new HashMap<>();
    String best = "";
    int bestN = 0;
    StringBuilder cur = new StringBuilder();
    for (int i = 0; i <= paragraph.length(); i++) {
        char c = i < paragraph.length() ? paragraph.charAt(i) : ' ';
        if (Character.isLetter(c)) {
            cur.append(c);
            continue;
        }
        if (cur.length() == 0) continue;
        String w = cur.toString().toLowerCase();
        cur.setLength(0);
        if (block.contains(w)) continue;
        int c2 = count.getOrDefault(w, 0) + 1;
        count.put(w, c2);
        if (c2 > bestN) { bestN = c2; best = w; }
    }
    return best;
}

C++

string mostCommonWord(string paragraph, vector<string>& banned) {
    unordered_set<string> block;
    for (string b : banned) {
        for (auto& ch : b) ch = (char) tolower(ch);
        block.insert(b);
    }
    unordered_map<string, int> count;
    string best = "", cur = "";
    int bestN = 0;
    for (size_t i = 0; i <= paragraph.size(); i++) {
        char c = i < paragraph.size() ? paragraph[i] : ' ';
        if (isalpha((unsigned char) c)) {
            cur += (char) tolower(c);
            continue;
        }
        if (cur.empty()) continue;
        string w = cur;
        cur.clear();
        if (block.count(w)) continue;
        int n = ++count[w];
        if (n > bestN) { bestN = n; best = w; }
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets