algoadvance

Leetcode 819. Most Common Word

Problem Statement

Given a paragraph and a list of banned words, return the most common 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.

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 common non-banned word in the paragraph.

Note:

• 1 <= paragraph.length <= 1000
• 1 <= banned.length <= 100
• 1 <= banned[i].length <= 10
• The answer is unique, and it is guaranteed that there is at least one word that isn’t banned.
• The paragraph only consists of letters, spaces, or the punctuation symbols: !?',;..
• There are no hyphens or underscores in the paragraph.
• Words are case-insensitive.
• The list of banned words is given in lowercase, and free of duplicates.

Clarifying Questions

• Should we consider punctuation and convert the entire paragraph to words only?
  • Yes, we should remove or ignore any punctuation.
• Is the case sensitivity a factor?
  • No, the words should be treated in a case-insensitive manner.

Strategy

1. Normalization: Convert the entire paragraph to lowercase to ensure consistency in comparison, and use regular expressions to split the paragraph into words.
2. Store Banned Words: Use a set to store banned words for O(1) lookup.
3. Count Frequencies: Create a frequency map (using unordered_map) to count the occurrences of each word that is not in the banned list.
4. Find the Most Common Word: Iterate over the frequency map to find the word with the highest occurrence that is not banned.

Code

#include <iostream>
#include <sstream>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <cctype>
#include <vector>
#include <algorithm>

using namespace std;

string mostCommonWord(string paragraph, vector<string>& banned) {
    // Step 1: Normalize paragraph to lowercase and parse words
    for (auto& c : paragraph) {
        if (isalpha(c)) {
            c = tolower(c);
        } else {
            c = ' ';
        }
    }

    // Step 2: Split paragraph into words
    istringstream stream(paragraph);
    string word;
    unordered_map<string, int> wordCount;
    unordered_set<string> bannedWords(banned.begin(), banned.end());

    // Step 3: Count words
    while (stream >> word) {
        if (bannedWords.find(word) == bannedWords.end()) {
            wordCount[word]++;
        }
    }

    // Step 4: Find the most common word
    string mostCommon;
    int maxCount = 0;

    for (const auto& [word, count] : wordCount) {
        if (count > maxCount) {
            mostCommon = word;
            maxCount = count;
        }
    }

    return mostCommon;
}

// Example usage
int main() {
    string paragraph = "Bob hit a ball, the hit BALL flew far after it was hit.";
    vector<string> banned = {"hit"};
    cout << mostCommonWord(paragraph, banned) << endl; // Should output "ball"
    return 0;
}

Time Complexity

• Normalization and Parsing: O(n), where n is the length of the paragraph.
• Storing Banned Words: O(b), where b is the number of banned words.
• Counting Frequencies: O(n), where n is the length of the paragraph.
• Finding the Most Common Word: O(w), where w is the number of unique words in the paragraph.

Overall, the time complexity of the algorithm is O(n + b + w), which simplifies to O(n) considering practical limits on paragraph length and word counts.

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?