Most Common Word

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.

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

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.

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();
    }
}