algoadvance

Leetcode 819. Most Common Word

Problem Statement:

Given a paragraph and a list of banned words, return the most frequent word that is not in the list of banned words. It is guaranteed there is at least one word that isn’t banned, and that the answer is unique.

• The words in the paragraph are case-insensitive and the answer should be returned in lowercase.
• The paragraph consists of lowercase letters, uppercase letters, spaces, or one of the following punctuation marks !?',;..
• Words are defined as a sequence of letters, separated by spaces or one of the aforementioned punctuation marks.

Clarifying Questions:

1. Input Format:
   • Is the input paragraph always a valid non-empty string?
     • Yes, assume it is always valid and non-empty.
   • Are banned words always a non-empty list of strings?
     • Yes.
2. Case Sensitivity:
   • Should we treat uppercase and lowercase letters as the same?
     • Yes, the comparison should be case-insensitive.
3. Expected Output:
   • Should the output be in lowercase?
     • Yes, the output should be in lowercase.

Strategy:

1. Clean the Paragraph:
   • Convert the entire paragraph to lowercase.
   • Replace all punctuation marks with spaces to simplify splitting the words.
2. Split into Words:
   • Split the paragraph into individual words based on spaces.
3. Filter Banned Words:
   • Use a set for the banned words to allow O(1) average-time complexity checks.
4. Count Word Frequencies:
   • Use a HashMap to count the occurrences of each word that is not banned.
5. Find Most Common Word:
   • Iterate through the HashMap to find the word with the highest frequency.

Code:

import java.util.*;

public class MostCommonWord {
    public String mostCommonWord(String paragraph, String[] banned) {
        Set<String> bannedSet = new HashSet<>(Arrays.asList(banned));
        Map<String, Integer> wordCount = new HashMap<>();

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

        // Count words that are not banned
        for (String word : words) {
            if (!bannedSet.contains(word)) {
                wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);
            }
        }

        // Find the most frequent word
        String mostCommon = null;
        int maxCount = 0;
        for (Map.Entry<String, Integer> entry : wordCount.entrySet()) {
            if (entry.getValue() > maxCount) {
                maxCount = entry.getValue();
                mostCommon = entry.getKey();
            }
        }

        return mostCommon;
    }

    public static void main(String[] args) {
        MostCommonWord solution = new MostCommonWord();
        String paragraph = "Bob hit a ball, the hit BALL flew far after it was hit.";
        String[] banned = {"hit"};
        System.out.println(solution.mostCommonWord(paragraph, banned));  // Output: "ball"
    }
}

Time Complexity:

• Preprocessing the Paragraph:
  • Normalizing the paragraph (converting to lowercase and replacing punctuation) takes O(n) where n is the length of the paragraph.
  • Splitting into words also takes O(n).
• Counting Word Frequencies:
  • Iterating over the words and updating the HashMap takes O(m), where m is the number of words in the paragraph.
• Finding the Most Frequent Word:
  • Iterating over the HashMap entries takes O(k), where k is the number of unique words.

Overall, the time complexity is O(n + m + k). Since m and k are bounded by n, the overall time complexity simplifies to O(n).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?