Most Common Word
Easy · Arrays & Hashing · Array · Hash Table · String · Counting
Problem
You are given a string paragraph and a list of strings banned. Return the most frequent word in paragraph that is not in banned. At least one word is not banned, and the answer is unique.
Words are case-insensitive and the answer is returned in lowercase. A word is a run of letters: spaces and the marks !?',;. separate words and are never part of one.
Examples
Input: paragraph = "Tea, coffee; TEA! the tea and the coffee, the end.", banned = ["tea"] Output: "the"
tea appears three times but is banned; the appears three times and coffee twice.
Input: paragraph = "Go. go? GO!", banned = [] Output: "go"
All three words are go.
Input: paragraph = "Bob's ball; bob hit the ball, then Bob ran.", banned = ["the"] Output: "bob"
Bob's is bob and s, so bob appears three times and ball twice.
Constraints
- 1 <= paragraph.length <= 1000
- paragraph has English letters, spaces and the marks !?',;.
- 0 <= banned.length <= 100
- 1 <= banned[i].length <= 10
- banned[i] has lowercase English letters only
Approaches
- Baseline: recount each word by scanning — time O(w² + w · m), space O(n)
Follow-up
Normalizing once and counting with a hash map is linear in the text. The use cases ask for the least common word (with an alphabetical tie-break) and the number of different words.
Related problems
Start free on Cariara · Coding problems · System design studio
