Approach #1: Counting [Accepted]

Intuition

This problem is about the implementation, as the question tells us how to solve the problem. We'll count each word separately, ignoring punctuation and converting each word to lowercase. The word with the highest frequency that isn't in the banned list is the answer.

Algorithm

We'll need some count of words (converted to lowercase) that we have seen in the paragraph. As we iterate through the paragraph, we will collect these words (with punctuation removed and converted to lowercase).

There are two ways we could try to collect these words: we could try to split the paragraph (delimited by spaces) and then clean up the fragment like "Bob!" to be "bob". Or, we could add characters one by one to build the next word, stopping when we reach a character that isn't a letter.

For each word (lowercase, and free of punctuation), we'll update our count and update the answer if the count of that word is highest (and the word is not banned.)

Complexity Analysis

  • Time Complexity: , where is the size of paragraph and is the size of banned.

  • Space Complexity: , to store the count and the banned set.


Analysis written by: @awice.