Most Common Word solution and explanation
Google
9 more videos on this problem
LeetCode Most Common Word Solution Explained - JavaNick White · 8:21 · 10K views
Most Common Word | LeetCode 819 | Amazon Coding Interview TutorialTerrible Whiteboard · 16:42 · 3K views
Most Common Word - LeetCode Solutions #819 (Python)Peter Hu · 5:18 · 2K views
Leetcode 819. Most Common Word PythonTechZoo · 3:02 · 1K views
Leetcode 819 - Most Common Word (JAVA Solution Explained!)LC Bear · 7:25 · 1K views
How to Solve "819 Most Common Word" on LeetCode? - JavascriptBecoming A Better Dev (with David) · 8:57 · 417 views
819. Most Common Word | LEETCODE EASY | STRINGcode Explainer · 7:59 · 386 views
LeetCode 819 - Most Common Word || Java SolutionV Codes · 6:30 · 320 views
Most Common Word | Leetcode - 819 | Approach + Code with explanation.Pirai's Academy · 12:54 · 315 views
Most Common Word - Leetcode 819 - JavascriptJunkCast7 · 13:02 · 193 views
The problem
Given a string paragraph and a string array of the banned words banned, return the most frequent word that is not banned. It is guaranteed there is at least one word that is not banned, and that the answer is unique.
The words in 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 frequent non-banned word in the paragraph. Note that words in the paragraph are not case sensitive, that punctuation is ignored (even if adjacent to words, such as "ball,"), and that "hit" isn't the answer even though it occurs more because it is banned.
Example 2:
Input: paragraph = "a.", banned = [] Output: "a"
Constraints:
1 <= paragraph.length <= 1000- paragraph consists of English letters, space
' ', or one of the symbols:"!?',;.". 0 <= banned.length <= 1001 <= banned[i].length <= 10banned[i]consists of only lowercase English letters.
Approach overview
Problem Overview: You receive a paragraph string and a list of banned words. The task is to return the most frequent word that is not banned. Words are case-insensitive and punctuation should be ignored, so parsing and normalization are key parts of the solution.
Approach 1: Frequency Count with HashMap (O(n) time, O(n) space)
This approach treats the paragraph as a stream of characters and builds words while scanning. Convert characters to lowercase and ignore punctuation. Each completed word is checked against a banned set using constant-time lookup. If the word is not banned, update its frequency in a HashMap (or dictionary). While counting, track the word with the highest frequency so you avoid a second pass over the map.
The key insight is that counting frequencies during a single pass over the text avoids repeated scanning. A hash-based structure gives O(1) average lookup for both banned checks and frequency updates. Total complexity is O(n) time where n is the paragraph length, and O(n) space for storing unique words. This approach relies heavily on hash table lookups and simple string processing.
Approach 2: Advanced String Manipulation and Collection (O(n) time, O(n) space)
This variation focuses on preprocessing the paragraph using string utilities. Replace punctuation characters with spaces, convert the text to lowercase, and split the paragraph into tokens. After tokenization, iterate through the resulting list of words and maintain counts in a map while skipping banned entries stored in a set.
The advantage of this approach is cleaner implementation in languages that support powerful string operations and collections. Splitting the text converts the problem into a straightforward array traversal with frequency counting. Each word update and banned lookup still runs in O(1) average time using hash structures. The overall complexity remains O(n) time and O(n) space because every character and token is processed once.
Recommended for interviews: The HashMap frequency counting approach is what most interviewers expect. It demonstrates that you can normalize input, use a banned set for fast filtering, and maintain counts efficiently with a map. Starting with the straightforward counting idea shows problem understanding, while implementing it in a single pass with proper string handling shows practical engineering skill.
Approach 1: Approach 1: Frequency Count with HashMap
This approach involves using a hash map to count the frequency of each word in the paragraph after converting it to lowercase and removing punctuation. Then, the word with the highest count that is not in the banned list is selected as the result.
from collections import Counter
import re
def most_common_word(paragraph, banned):
banned_set = set(banned)
words = re.findall(r'\w+', paragraph.lower())
word_count = Counter(word for word in words if word not in banned_set)
return word_count.most_common(1)[0][0]
paragraph = "Bob hit a ball, the hit BALL flew far after it was hit."
banned = ["hit"]
print(most_common_word(paragraph, banned))import java.util.*;
public class Main {
public static String mostCommonWord(String paragraph, String[] banned) {
Set<String> bannedSet = new HashSet<>(Arrays.asList(banned));
Map<String, Integer> wordFreq = new HashMap<>();
String[] words = paragraph.replaceAll("[^a-zA-Z ]", " ").toLowerCase().split("\s+");
String result = "";
int maxCount = 0;
for (String word : words) {
if (!bannedSet.contains(word)) {
wordFreq.put(word, wordFreq.getOrDefault(word, 0) + 1);
if (wordFreq.get(word) > maxCount) {
maxCount = wordFreq.get(word);
result = word;
}
}
}
return result;
}
public static void main(String[] args) {
String paragraph = "Bob hit a ball, the hit BALL flew far after it was hit.";
String[] banned = {"hit"};
System.out.println(mostCommonWord(paragraph, banned));
}
}#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <sstream>
#include <algorithm>
std::string mostCommonWord(std::string paragraph, std::vector<std::string>& banned) {
std::unordered_set<std::string> bannedSet(banned.begin(), banned.end());
std::unordered_map<std::string, int> wordFreq;
std::string word, result;
int maxCount = 0;
for (auto& c : paragraph) {
c = isalpha(c) ? tolower(c) : ' ';
}
std::istringstream iss(paragraph);
while (iss >> word) {
if (bannedSet.find(word) == bannedSet.end()) {
wordFreq[word]++;
if (wordFreq[word] > maxCount) {
maxCount = wordFreq[word];
result = word;
}
}
}
return result;
}
int main() {
std::vector<std::string> banned = {"hit"};
std::string paragraph = "Bob hit a ball, the hit BALL flew far after it was hit.";
std::cout << mostCommonWord(paragraph, banned) << std::endl;
return 0;
}function mostCommonWord(paragraph, banned) {
const bannedSet = new Set(banned);
const words = paragraph.toLowerCase().match(/\w+/g);
const wordCount = {};
for (const word of words) {
if (!bannedSet.has(word)) {
wordCount[word] = (wordCount[word] || 0) + 1;
}
}
let maxWord = '';
let maxCount = 0;
for (const [word, count] of Object.entries(wordCount)) {
if (count > maxCount) {
maxWord = word;
maxCount = count;
}
}
return maxWord;
}
const paragraph = "Bob hit a ball, the hit BALL flew far after it was hit.";
const banned = ["hit"];
console.log(mostCommonWord(paragraph, banned));#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#define MAX_WORD_LENGTH 100
#define MAX_PARAGRAPH_LENGTH 1000
typedef struct {
char word[MAX_WORD_LENGTH];
int count;
} WordFrequency;
int isBanned(const char* word, const char** banned, int bannedSize) {
for (int i = 0; i < bannedSize; i++) {
if (strcmp(word, banned[i]) == 0) {
return 1;
}
}
return 0;
}
char* mostCommonWord(char* paragraph, const char** banned, int bannedSize) {
WordFrequency wordFreq[MAX_PARAGRAPH_LENGTH] = {0};
char* result = NULL;
int maxCount = 0;
int wordFreqSize = 0;
char delimiters[] = " !?',;.",
*token = strtok(paragraph, delimiters);
while (token != NULL) {
char word[MAX_WORD_LENGTH];
strcpy(word, token);
for (int i = 0; word[i]; i++) {
word[i] = tolower(word[i]);
}
if (!isBanned(word, banned, bannedSize)) {
int found = 0;
for (int i = 0; i < wordFreqSize; i++) {
if (strcmp(wordFreq[i].word, word) == 0) {
wordFreq[i].count++;
found = 1;
break;
}
}
if (!found) {
strcpy(wordFreq[wordFreqSize].word, word);
wordFreq[wordFreqSize].count = 1;
wordFreqSize++;
}
}
token = strtok(NULL, delimiters);
}
for (int i = 0; i < wordFreqSize; i++) {
if (wordFreq[i].count > maxCount) {
maxCount = wordFreq[i].count;
result = wordFreq[i].word;
}
}
return result;
}
int main() {
const char* banned[] = {"hit"};
char paragraph[] = "Bob hit a ball, the hit BALL flew far after it was hit.";
printf("%s\n", mostCommonWord(paragraph, banned, 1));
return 0;
}using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
class Program {
public static string MostCommonWord(string paragraph, string[] banned) {
var bannedSet = new HashSet<string>(banned);
var wordCounts = new Dictionary<string, int>();
var words = Regex.Matches(paragraph.ToLower(), "\b\w+\b");
foreach (Match match in words) {
var word = match.Value;
if (!bannedSet.Contains(word)) {
if (!wordCounts.ContainsKey(word)) {
wordCounts[word] = 0;
}
wordCounts[word]++;
}
}
return wordCounts.OrderByDescending(kvp => kvp.Value).First().Key;
}
static void Main() {
string paragraph = "Bob hit a ball, the hit BALL flew far after it was hit.";
string[] banned = {"hit"};
Console.WriteLine(MostCommonWord(paragraph, banned));
}
}This Python solution uses regular expressions to extract words from the paragraph, counts their frequencies with collections.Counter, and ignores banned words. most_common method is used to find the most frequent non-banned word.
Time Complexity: O(N + M), where N is the number of characters in the paragraph, and M is the number of banned words. Space Complexity: O(N).
Approach 2: Approach 2: Advanced String Manipulation and Collection
This approach leverages advanced string manipulation functions available in each language for efficient parsing and counting. The words are extracted, normalized, and counted using advanced language-specific methods and libraries for cleaner code.
from collections import Counter
import re
def most_common_word(paragraph, banned):
banned_set = set(banned)
words = re.findall(r'\w+', paragraph.lower())
word_count = Counter(word for word in words if word not in banned_set)
return max(word_count, key=word_count.get)
paragraph = "Bob hit a ball, the hit BALL flew far after it was hit."
banned = ["hit"]
print(most_common_word(paragraph, banned))import java.util.*;
public class Main {
public static String mostCommonWord(String paragraph, String[] banned) {
Set<String> bannedSet = new HashSet<>(Arrays.asList(banned));
Map<String, Integer> wordFreq = new HashMap<>();
String[] words = paragraph.toLowerCase().replaceAll("[^a-z]+", " ").split("\\s+");
for (String word : words) {
if (!bannedSet.contains(word)) {
wordFreq.put(word, wordFreq.getOrDefault(word, 0) + 1);
}
}
return Collections.max(wordFreq.entrySet(), Map.Entry.comparingByValue()).getKey();
}
public static void main(String[] args) {
String paragraph = "Bob hit a ball, the hit BALL flew far after it was hit.";
String[] banned = {"hit"};
System.out.println(mostCommonWord(paragraph, banned));
}
}#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <sstream>
#include <algorithm>
std::string mostCommonWord(std::string paragraph, std::vector<std::string>& banned) {
std::unordered_set<std::string> bannedSet(banned.begin(), banned.end());
std::unordered_map<std::string, int> wordFreq;
std::string word, result;
for (auto& c : paragraph) {
c = isalpha(c) ? tolower(c) : ' ';
}
std::istringstream iss(paragraph);
while (iss >> word) {
if (bannedSet.find(word) == bannedSet.end()) {
wordFreq[word]++;
}
}
return std::max_element(wordFreq.begin(), wordFreq.end(),
[](const auto& a, const auto& b) {
return a.second < b.second;
})->first;
}
int main() {
std::vector<std::string> banned = {"hit"};
std::string paragraph = "Bob hit a ball, the hit BALL flew far after it was hit.";
std::cout << mostCommonWord(paragraph, banned) << std::endl;
return 0;
}function mostCommonWord(paragraph, banned) {
const bannedSet = new Set(banned);
const words = paragraph.toLowerCase().match(/\w+/g);
const wordCount = {};
for (const word of words) {
if (!bannedSet.has(word)) {
wordCount[word] = (wordCount[word] || 0) + 1;
}
}
return Object.entries(wordCount).reduce((maxWord, curr) => curr[1] > maxWord[1] ? curr : maxWord, ['', 0])[0];
}
const paragraph = "Bob hit a ball, the hit BALL flew far after it was hit.";
const banned = ["hit"];
console.log(mostCommonWord(paragraph, banned));#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#define MAX_WORD_LENGTH 100
#define MAX_PARAGRAPH_LENGTH 1000
typedef struct {
char word[MAX_WORD_LENGTH];
int count;
} WordFrequency;
// Assuming auxiliary functions (e.g., sort or search) are predefined for simplicity in C
int sortByFrequencyDesc(const void *a, const void *b) {
WordFrequency *x = (WordFrequency *)a;
WordFrequency *y = (WordFrequency *)b;
return y->count - x->count;
}
int isBanned(const char* word, const char** banned, int bannedSize) {
for (int i = 0; i < bannedSize; i++) {
if (strcmp(word, banned[i]) == 0) {
return 1;
}
}
return 0;
}
char* mostCommonWord(char* paragraph, const char** banned, int bannedSize) {
WordFrequency wordFreq[MAX_PARAGRAPH_LENGTH] = {0};
char delimiters[] = " !?',;.",
*token = strtok(paragraph, delimiters);
int wordFreqSize = 0;
while (token != NULL) {
char word[MAX_WORD_LENGTH];
strcpy(word, token);
for (int i = 0; word[i]; i++) {
word[i] = tolower(word[i]);
}
if (!isBanned(word, banned, bannedSize)) {
int found = 0;
for (int i = 0; i < wordFreqSize; i++) {
if (strcmp(wordFreq[i].word, word) == 0) {
wordFreq[i].count++;
found = 1;
break;
}
}
if (!found) {
strcpy(wordFreq[wordFreqSize].word, word);
wordFreq[wordFreqSize].count = 1;
wordFreqSize++;
}
}
token = strtok(NULL, delimiters);
}
qsort(wordFreq, wordFreqSize, sizeof(WordFrequency), sortByFrequencyDesc);
return wordFreq[0].word;
}
int main() {
const char* banned[] = {"hit"};
char paragraph[] = "Bob hit a ball, the hit BALL flew far after it was hit.";
printf("%s\n", mostCommonWord(paragraph, banned, 1));
return 0;
}using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
class Program {
public static string MostCommonWord(string paragraph, string[] banned) {
var bannedSet = new HashSet<string>(banned);
var wordCounts = new Dictionary<string, int>();
var words = Regex.Matches(paragraph.ToLower(), "\b\w+\b");
foreach (Match match in words) {
var word = match.Value;
if (!bannedSet.Contains(word)) {
if (!wordCounts.ContainsKey(word)) {
wordCounts[word] = 0;
}
wordCounts[word]++;
}
}
return wordCounts.Aggregate((a, b) => a.Value > b.Value ? a : b).Key;
}
static void Main() {
string paragraph = "Bob hit a ball, the hit BALL flew far after it was hit.";
string[] banned = {"hit"};
Console.WriteLine(MostCommonWord(paragraph, banned));
}
}This Python approach leverages Counter and re.findall for succinctly parsing and counting words, followed by determining the max occurrence non-banned word using the max function with a key parameter.
Time Complexity: O(N + M). Space Complexity: O(N).
Approach 3: Default Approach
function mostCommonWord(paragraph: string, banned: string[]): string {
const s = paragraph.toLocaleLowerCase();
const map = new Map<string, number>();
const set = new Set<string>(banned);
for (const word of s.split(/[^A-z]/)) {
if (word === '' || set.has(word)) {
continue;
}
map.set(word, (map.get(word) ?? 0) + 1);
}
return [...map.entries()].reduce((r, v) => (v[1] > r[1] ? v : r), ['', 0])[0];
}func mostCommonWord(paragraph string, banned []string) string {
s := make(map[string]bool)
for _, w := range banned {
s[w] = true
}
counter := make(map[string]int)
var ans string
for i, mx, n := 0, 0, len(paragraph); i < n; {
if !unicode.IsLetter(rune(paragraph[i])) {
i++
continue
}
j := i
var word []byte
for j < n && unicode.IsLetter(rune(paragraph[j])) {
word = append(word, byte(unicode.ToLower(rune(paragraph[j]))))
j++
}
i = j + 1
t := string(word)
if s[t] {
continue
}
counter[t]++
if counter[t] > mx {
ans = t
mx = counter[t]
}
}
return ans
}use std::collections::{HashMap, HashSet};
impl Solution {
pub fn most_common_word(mut paragraph: String, banned: Vec<String>) -> String {
paragraph.make_ascii_lowercase();
let banned: HashSet<&str> = banned.iter().map(String::as_str).collect();
let mut map = HashMap::new();
for word in paragraph.split(|c| !matches!(c, 'a'..='z')) {
if word.is_empty() || banned.contains(word) {
continue;
}
let val = map.get(&word).unwrap_or(&0) + 1;
map.insert(word, val);
}
map.into_iter()
.max_by_key(|&(_, v)| v)
.unwrap()
.0
.to_string()
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Frequency Count with HashMap | Time Complexity: O(N + M), where N is the number of characters in the paragraph, and M is the number of banned words. Space Complexity: O(N). |
| Approach 2: Advanced String Manipulation and Collection | Time Complexity: O(N + M). Space Complexity: O(N). |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Frequency Count with HashMap | O(n) | O(n) | General case. Efficient single-pass solution commonly expected in coding interviews. |
| Advanced String Manipulation and Collection | O(n) | O(n) | Useful when the language provides convenient string replace and split utilities. |
Frequently asked questions
Is Most Common Word easy or hard?
Most Common Word is classified as an Easy problem on LeetCode. The challenge mainly involves correct string parsing, ignoring punctuation, and applying hash map frequency counting efficiently.
Most Common Word Python/Java solution
In Python, use a dictionary for counting and a set for banned words while parsing the string. In Java, use HashMap<String, Integer> for frequencies and HashSet<String> for banned checks. Both implementations follow the same O(n) time and O(n) space logic.
How to solve Most Common Word in O(n)?
Scan the paragraph character by character, converting letters to lowercase and skipping punctuation. Build words incrementally and check them against a banned set. For each valid word, increment its count in a hash map and track the maximum frequency. This single-pass counting approach achieves O(n) time complexity.
What is the best approach for Most Common Word?
The most efficient approach uses a HashMap for frequency counting and a HashSet for banned words. Parse the paragraph, normalize characters to lowercase, ignore punctuation, and update counts for each valid word. This method processes the paragraph in a single pass with O(n) time complexity and O(n) space.
Is Most Common Word asked at Google/Amazon/Meta?
This problem pattern appears frequently in interviews at large tech companies such as Amazon and Google. It tests practical skills like string parsing, hash map usage, and handling edge cases with punctuation and case normalization.
What data structure is used in Most Common Word?
The core data structures are a HashMap (or dictionary) to store word frequencies and a HashSet to store banned words. These structures provide constant-time average lookups, which makes the overall algorithm efficient.
What is the time complexity of Most Common Word?
The optimal solution runs in O(n) time where n is the length of the paragraph. Each character is processed once while building words and updating frequencies. Hash map insertions and lookups run in average O(1), so the total runtime remains linear.