Most Common Word - Practice Coding Problems

Most Common Word - Problem

Given a string paragraph and a string array of the banned words, 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.

Note: Words cannot contain punctuation symbols.

Input & Output

Example 1 — Basic Case

$ Input: paragraph = "Bob hit a ball, the hit BALL flew far after it was hit.", banned = ["hit"]

› Output: "ball"

💡 Note: "hit" appears 3 times but is banned. "ball" appears 2 times (case-insensitive: "ball", "BALL") and is not banned, making it the most frequent valid word.

Example 2 — Multiple Banned Words

$ Input: paragraph = "a, a, a, a, b,b,b,c, c", banned = ["a"]

› Output: "b"

💡 Note: "a" appears 4 times but is banned. "b" appears 3 times and "c" appears 2 times. "b" is the most frequent non-banned word.

Example 3 — Case Insensitive

$ Input: paragraph = "Bob bob BOB", banned = []

› Output: "bob"

💡 Note: "Bob", "bob", and "BOB" are the same word (case-insensitive). "bob" appears 3 times and no words are banned.

Constraints

1 ≤ paragraph.length ≤ 1000
paragraph consists of English letters, space ' ', or one of the symbols: "!?',;."
0 ≤ banned.length ≤ 100
1 ≤ banned[i].length ≤ 10
banned[i] consists of only lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

Raw paragraph with punctuation and banned words list

Process

Clean text, extract words, count frequencies, filter banned

Output

Most frequent word that's not in banned list

Key Takeaway

🎯 Key Insight: Use hash maps for efficient frequency counting and banned word filtering in a single pass

Asked in

A Amazon 45 🍎 Apple 32 G Google 28 F Facebook 21

The key insight is to use hash maps for both frequency counting and banned word filtering. Extract words using regex, count frequencies while skipping banned words, then find the maximum. Best approach is single pass with immediate filtering for optimal performance. Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Manual Word Processing	O(n × m)	O(n)	Manually extract words, count each occurrence, and find maximum non-banned word
Hash Map Frequency Count	O(n + m)	O(n + k)	Single pass to count word frequencies using hash map, then find maximum non-banned word
Single Pass with Immediate Filtering	O(n)	O(n + k)	Count frequencies while immediately filtering banned words during parsing

Brute Force - Manual Word Processing — Algorithm Steps

Extract all words by iterating through each character
For each unique word, scan entire text again to count occurrences
Skip banned words and find the word with maximum count

Visualization

Tap to expand

Step-by-Step Walkthrough

Extract Words

Split paragraph into individual words

Count Each

For each unique word, scan entire text to count occurrences

Find Maximum

Return non-banned word with highest count

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define MAX_WORDS 1000
#define MAX_WORD_LEN 100
#define MAX_TEXT_LEN 10000

char* solution(char* paragraph, char banned[][MAX_WORD_LEN], int bannedSize) {
    char words[MAX_WORDS][MAX_WORD_LEN];
    int wordCount = 0;
    
    // Extract words
    int len = strlen(paragraph);
    int wordStart = -1;
    
    for (int i = 0; i <= len; i++) {
        if (i < len && isalpha(paragraph[i])) {
            if (wordStart == -1) wordStart = i;
        } else {
            if (wordStart != -1) {
                int wordLen = i - wordStart;
                for (int j = 0; j < wordLen; j++) {
                    words[wordCount][j] = tolower(paragraph[wordStart + j]);
                }
                words[wordCount][wordLen] = '\0';
                wordCount++;
                wordStart = -1;
            }
        }
    }
    
    int maxCount = 0;
    char* result = malloc(MAX_WORD_LEN);
    result[0] = '\0';
    
    // For each unique word, count occurrences
    int seen[MAX_WORDS] = {0};
    for (int i = 0; i < wordCount; i++) {
        if (seen[i]) continue;
        
        // Check if banned
        int isBanned = 0;
        for (int j = 0; j < bannedSize; j++) {
            if (strcmp(words[i], banned[j]) == 0) {
                isBanned = 1;
                break;
            }
        }
        if (isBanned) continue;
        
        // Count occurrences
        int count = 0;
        for (int j = 0; j < wordCount; j++) {
            if (strcmp(words[i], words[j]) == 0) {
                count++;
                seen[j] = 1;
            }
        }
        
        if (count > maxCount) {
            maxCount = count;
            strcpy(result, words[i]);
        }
    }
    
    return result;
}

int main() {
    char paragraph[MAX_TEXT_LEN];
    fgets(paragraph, sizeof(paragraph), stdin);
    paragraph[strcspn(paragraph, "\n")] = 0;
    
    char bannedLine[MAX_TEXT_LEN];
    fgets(bannedLine, sizeof(bannedLine), stdin);
    bannedLine[strcspn(bannedLine, "\n")] = 0;
    
    // Parse banned array
    char banned[100][MAX_WORD_LEN];
    int bannedSize = 0;
    
    if (strlen(bannedLine) > 2) {
        char* token = strtok(bannedLine + 1, ",]");
        while (token != NULL && bannedSize < 100) {
            while (*token == ' ' || *token == '"') token++;
            char* end = token + strlen(token) - 1;
            while (end > token && (*end == ' ' || *end == '"')) end--;
            *(end + 1) = '\0';
            
            if (strlen(token) > 0) {
                strcpy(banned[bannedSize], token);
                bannedSize++;
            }
            token = strtok(NULL, ",]");
        }
    }
    
    char* result = solution(paragraph, banned, bannedSize);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m)

For each of m unique words, we scan the entire text of length n to count occurrences

✓ Linear Growth

Space Complexity

O(n)

Store all extracted words and banned words set

⚡ Linearithmic Space

28.4K Views

Medium Frequency

~15 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Manual Word Processing — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler