# Most Common Word
**Difficulty:** EASY
[External](https://leetcode.com/problems/most-common-word)
Canonical: https://scaleengineer.com/dsa/problems/most-common-word
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Array, Hash Table, String
**Companies:** [Datadog](https://scaleengineer.com/companies/datadog)
---
## Problem
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
## Brute Force with List for Banned Words
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.
**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.
**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.
### Explanation
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.

```java
import java.util.HashMap;
import java.util.Map;
import java.util.Arrays;
import java.util.List;

class Solution {
    public String mostCommonWord(String paragraph, String[] banned) {
        // Convert banned array to a list for easier lookup (though still O(M))
        List<String> bannedList = Arrays.asList(banned);

        // Normalize and split the paragraph into words
        String[] words = paragraph.toLowerCase().split("[\\s!?',;.]+");

        Map<String, Integer> wordCounts = new HashMap<>();
        for (String word : words) {
            if (word.isEmpty()) {
                continue;
            }
            // Inefficient check against the banned list
            if (!bannedList.contains(word)) {
                wordCounts.put(word, wordCounts.getOrDefault(word, 0) + 1);
            }
        }

        // Find the most frequent word
        String result = "";
        int maxCount = 0;
        for (Map.Entry<String, Integer> entry : wordCounts.entrySet()) {
            if (entry.getValue() > maxCount) {
                maxCount = entry.getValue();
                result = entry.getKey();
            }
        }
        return result;
    }
}
```
### 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.

## Optimized Approach with Hash Set
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.
**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.
**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.
### Explanation
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.

```java
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.HashSet;
import java.util.Arrays;
import java.util.Collections;

class Solution {
    public String mostCommonWord(String paragraph, String[] banned) {
        // 1. Store Banned Words in a Set for O(1) lookups
        Set<String> bannedSet = new HashSet<>(Arrays.asList(banned));

        // 2. Normalize and Split Paragraph
        String[] words = paragraph.toLowerCase().split("[\\s!?',;.]+");

        // 3. Count Word Frequencies
        Map<String, Integer> wordCounts = new HashMap<>();
        for (String word : words) {
            if (!word.isEmpty() && !bannedSet.contains(word)) {
                wordCounts.put(word, wordCounts.getOrDefault(word, 0) + 1);
            }
        }

        // 4. Find Most Frequent Word
        // The problem guarantees an answer exists, so the map is not empty.
        return Collections.max(wordCounts.entrySet(), Map.Entry.comparingByValue()).getKey();
    }
}
```
### 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.

# Solutions
### Java

```java
import 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 ; } }
```

### CPP

```cpp
class Solution {
public:
  string mostCommonWord(string paragraph, vector<string> &banned) {
    unordered_set<string> s(banned.begin(), banned.end());
    unordered_map<string, int> counter;
    string ans;
    for (int i = 0, mx = 0, n = paragraph.size(); i < n;) {
      if (!isalpha(paragraph[i]) && (++i > 0))
        continue;
      int j = i;
      string word;
      while (j < n && isalpha(paragraph[j])) {
        word.push_back(tolower(paragraph[j]));
        ++j;
      }
      i = j + 1;
      if (s.count(word))
        continue;
      ++counter[word];
      if (counter[word] > mx) {
        ans = word;
        mx = counter[word];
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    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)

```