Approach #1: Counting [Accepted]
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.
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.)
Time Complexity: , where is the size of
paragraphand is the size of
Space Complexity: , to store the
countand the banned set.