Most Common Word

Easy

#0773Time: O(N + C), where N is the number of characters in the paragraph and C is the total number of characters in the `banned` list. Creating the set is O(C), processing the paragraph is O(N), and counting words is O(N). This is linear in the total input size.Space: O(N + C), where N is the number of characters in the paragraph and C is the total number of characters in the `banned` list. Space is required for the `bannedSet` and the `wordCounts` map.1 company

Patterns

Counting

Data structures

Array Hash Table String

Companies

Datadog

Prompt

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

The words in paragraph are case-insensitive and the answer should be returned in lowercase.

Note that words can not contain punctuation symbols.

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 no other word does), so it is the most frequent non-banned word in the paragraph. 
Note that words in the paragraph are not case sensitive,
that punctuation is ignored (even if adjacent to words, such as "ball,"), 
and that "hit" isn't the answer even though it occurs more because it is banned.

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
1 <= banned[i].length <= 10
banned[i] consists of only lowercase English letters.

Approaches

2 approaches with complexity analysis and trade-offs.

This is the standard and most efficient approach. It improves upon the brute-force method by using a HashSet to store the banned words. This allows for checking if a word is banned in constant average time, significantly speeding up the process.

Algorithm

Create a HashSet<String> from the banned array to store banned words for efficient lookup.
Normalize the paragraph by converting it to lowercase and splitting it into an array of words using spaces and punctuation as delimiters ([\s!?',;.]+).
Initialize a HashMap<String, Integer> to store the frequencies of non-banned words.
Iterate through each word from the split paragraph.
For each word, check if it is present in the banned set. This check has an average time complexity of O(1).
If the word is not empty and not in the banned set, update its count in the HashMap.
After populating the map, find the entry with the maximum value. This can be done efficiently using Collections.max() with a custom comparator.
Return the key (the word) of the entry with the highest frequency.

Walkthrough

This optimized solution leverages the strengths of hash-based data structures to achieve linear time complexity. First, the banned words are added to a HashSet. This is a crucial step, as it allows us to check if a word is banned in O(1) average time, a massive improvement over the linear scan of a list.

Next, the paragraph is normalized. It's converted to lowercase, and then all punctuation is effectively removed by splitting the string by a regular expression that matches any sequence of spaces or punctuation marks. This gives us a clean array of words.

We then iterate through these words. For each word, we perform a quick check against the bannedSet. If the word is not banned, we update its frequency in a HashMap. Finally, instead of manually iterating to find the maximum frequency, we can use the elegant Collections.max() method on the map's entry set to find the most common word in a single line.

1import java.util.HashMap;2import java.util.Map;3import java.util.Set;4import java.util.HashSet;5import java.util.Arrays;6import java.util.Collections;7 8class Solution {9    public String mostCommonWord(String paragraph, String[] banned) {10        // 1. Store Banned Words in a Set for O(1) lookups11        Set<String> bannedSet = new HashSet<>(Arrays.asList(banned));12 13        // 2. Normalize and Split Paragraph14        String[] words = paragraph.toLowerCase().split("[\\s!?',;.]+");15 16        // 3. Count Word Frequencies17        Map<String, Integer> wordCounts = new HashMap<>();18        for (String word : words) {19            if (!word.isEmpty() && !bannedSet.contains(word)) {20                wordCounts.put(word, wordCounts.getOrDefault(word, 0) + 1);21            }22        }23 24        // 4. Find Most Frequent Word25        // The problem guarantees an answer exists, so the map is not empty.26        return Collections.max(wordCounts.entrySet(), Map.Entry.comparingByValue()).getKey();27    }28}

Complexity

Time

O(N + C), where N is the number of characters in the paragraph and C is the total number of characters in the `banned` list. Creating the set is O(C), processing the paragraph is O(N), and counting words is O(N). This is linear in the total input size.

Space

O(N + C), where N is the number of characters in the paragraph and C is the total number of characters in the `banned` list. Space is required for the `bannedSet` and the `wordCounts` map.

Trade-offs

Pros

Highly efficient with a linear time complexity relative to the total input size.
Optimal use of data structures (HashSet, HashMap) for their respective tasks (fast lookups and frequency counting).
The code is clean, concise, and scalable for larger inputs.

Cons

Requires slightly more memory to store the HashSet for banned words, though this is a worthwhile trade-off for the significant performance improvement.

This approach involves processing the paragraph to extract words, and then for each word, iterating through the entire list of banned words to check if it should be counted. This leads to a less efficient solution due to the repeated linear scan of the banned list.

Algorithm

Convert the banned array into a List for easier checking.
Normalize the paragraph by converting it to lowercase and splitting it into words based on spaces and punctuation. The delimiters used for splitting would be [\s!?',;.]+.
Initialize a HashMap<String, Integer> to store the frequency of each word.
Iterate through each word from the split paragraph.
For each word, check if it is present in the banned list. This check is a linear scan, making it inefficient.
If the word is not empty and not in the banned list, update its count in the HashMap.
After counting, iterate through the HashMap to find the word with the highest frequency.
Return the most frequent word found.

Walkthrough

This method takes a straightforward, brute-force path to solving the problem. First, it prepares the data by converting the banned array into a List and normalizing the input paragraph. Normalization involves converting the text to lowercase and then splitting it into an array of words using spaces and punctuation as delimiters.

The core of this approach is a loop over the extracted words. Inside this loop, for each word, it checks if the word is in the banned list using list.contains(), which performs a linear search. If a word is not banned, its frequency is tracked in a HashMap. Finally, another iteration over the frequency map is required to identify and return the word with the highest count.

1import java.util.HashMap;2import java.util.Map;3import java.util.Arrays;4import java.util.List;5 6class Solution {7    public String mostCommonWord(String paragraph, String[] banned) {8        // Convert banned array to a list for easier lookup (though still O(M))9        List<String> bannedList = Arrays.asList(banned);10 11        // Normalize and split the paragraph into words12        String[] words = paragraph.toLowerCase().split("[\\s!?',;.]+");13 14        Map<String, Integer> wordCounts = new HashMap<>();15        for (String word : words) {16            if (word.isEmpty()) {17                continue;18            }19            // Inefficient check against the banned list20            if (!bannedList.contains(word)) {21                wordCounts.put(word, wordCounts.getOrDefault(word, 0) + 1);22            }23        }24 25        // Find the most frequent word26        String result = "";27        int maxCount = 0;28        for (Map.Entry<String, Integer> entry : wordCounts.entrySet()) {29            if (entry.getValue() > maxCount) {30                maxCount = entry.getValue();31                result = entry.getKey();32            }33        }34        return result;35    }36}

Complexity

Time

O(N + W * M * L), where N is the number of characters in the paragraph, W is the number of words in the paragraph, M is the number of banned words, and L is the average length of a word. The bottleneck is the `W * M * L` term from checking each of the W words against the M banned words.

Space

O(N + C), where N is the number of characters in the paragraph and C is the total characters in the `banned` array. Space is needed for the words from the paragraph and the word counts map.

Trade-offs

Pros

Conceptually simple and easy to understand.
Implementation is straightforward without requiring knowledge of more complex data structures like Hash Sets.

Cons

Highly inefficient due to the repeated linear scan of the banned list. For every word in the paragraph, the entire banned list is traversed.
The time complexity is pseudo-polynomial, making it slow for inputs with a large number of words or a long list of banned words.

Solutions

Solution

1import java.util.regex.Matcher ; import java.util.regex.Pattern ; class Solution { private static Pattern pattern = Pattern . compile ( "[a-z]+" ); public String mostCommonWord ( String paragraph , String [] banned ) { Set < String > bannedWords = new HashSet <>(); for ( String word : banned ) { bannedWords . add ( word ); } Map < String , Integer > counter = new HashMap <>(); Matcher matcher = pattern . matcher ( paragraph . toLowerCase ()); while ( matcher . find ()) { String word = matcher . group (); if ( bannedWords . contains ( word )) { continue ; } counter . put ( word , counter . getOrDefault ( word , 0 ) + 1 ); } int max = Integer . MIN_VALUE ; String ans = null ; for ( Map . Entry < String , Integer > entry : counter . entrySet ()) { if ( entry . getValue () > max ) { max = entry . getValue (); ans = entry . getKey (); } } return ans ; } }

1class Solution {2public:3  string mostCommonWord(string paragraph, vector<string> &banned) {4    unordered_set<string> s(banned.begin(), banned.end());5    unordered_map<string, int> counter;6    string ans;7    for (int i = 0, mx = 0, n = paragraph.size(); i < n;) {8      if (!isalpha(paragraph[i]) && (++i > 0))9        continue;10      int j = i;11      string word;12      while (j < n && isalpha(paragraph[j])) {13        word.push_back(tolower(paragraph[j]));14        ++j;15      }16      i = j + 1;17      if (s.count(word))18        continue;19      ++counter[word];20      if (counter[word] > mx) {21        ans = word;22        mx = counter[word];23      }24    }25    return ans;26  }27};

1class Solution:2    def mostCommonWord(self, paragraph: str, banned: List[str]) -> str: s = set(banned) p = Counter(re . findall('[a-z]+', paragraph . lower())) return next(word for word, _ in p . most_common() if word not in s)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem