Report Spam Message solution and explanation
IBM
8 more videos on this problem
Report Spam Message || LeetCode Weekly Contest 416 || Leetcode Solutioncodi · 0:37 · 611 views
Leetcode | 3295. Report Spam Message | Medium | JavaDeveloper Docs · 3:55 · 425 views
3295. Report Spam Message (Leetcode Medium)Programming Live with Larry · 2:57 · 341 views
Report Spam Message - LEETCODE WEEKLY CONTEST 416Joyjit Codes · 1:30 · 166 views
LeetCode Weekly Contest 416 | 3295. Report Spam Message | Efficient Solution with ExplanationTushar Awasthi · 2:05 · 147 views
LeetCode 3295: Report Spam Message | Weekly Contest 416 | C++ Solution ExplainedDebugAndDeploy · 7:25 · 117 views
Report Spam Message Leetcode Question No : 3295StackWatt · 6:19 · 27 views
Leetcode 3295 Report Spam Message - Explained In HindiAlgorithmicIQ · 8:09 · 21 views
Copy of 3295. Report Spam MessageCoder@Dixit · 17:45 · 20 views
The problem
You are given an array of strings message and an array of strings bannedWords.
An array of words is considered spam if there are at least two words in it that exactly match any word in bannedWords.
Return true if the array message is spam, and false otherwise.
Example 1:
Input: message = ["hello","world","leetcode"], bannedWords = ["world","hello"]
Output: true
Explanation:
The words "hello" and "world" from the message array both appear in the bannedWords array.
Example 2:
Input: message = ["hello","programming","fun"], bannedWords = ["world","programming","leetcode"]
Output: false
Explanation:
Only one word from the message array ("programming") appears in the bannedWords array.
Constraints:
1 <= message.length, bannedWords.length <= 1051 <= message[i].length, bannedWords[i].length <= 15message[i]andbannedWords[i]consist only of lowercase English letters.
Approach overview
Problem Overview: You receive a message represented as an array of words and another list containing banned words. The task is to determine whether the message should be reported as spam. A message is considered spam if at least two words from the message appear in the banned list.
Approach 1: Hash Set for Fast Lookup (O(n + m) time, O(m) space)
The most practical solution converts the banned word list into a hash set. This gives constant-time membership checks. First iterate through the banned array and insert each word into the set. Then iterate through the message words and check whether each word exists in the set using a hash lookup. Maintain a counter for matches and stop once the count reaches two.
The key insight is that repeated membership checks become expensive if the banned list is scanned each time. A hash set reduces that lookup from O(m) to O(1). The total complexity becomes O(n + m), where n is the number of words in the message and m is the size of the banned list. Space complexity is O(m) for the set. This pattern appears frequently in problems involving fast membership checks on hash tables and word matching across arrays.
Approach 2: Frequency Count with Early Exit (O(n + m) time, O(m) space)
Another way is to track occurrences of banned words using a frequency structure. Build a hash map or set from the banned list, then iterate through the message while counting matches. As soon as the second banned word is encountered, immediately return true. This early exit avoids scanning the entire message when spam is detected early.
This approach behaves similarly to the hash set strategy but emphasizes counting and early termination. The algorithm still performs a single pass through the message with constant-time lookups. Time complexity remains O(n + m), and space complexity stays O(m). Early termination often improves real-world performance when spam appears near the beginning of the message.
Both solutions rely on efficient word comparison and are common in moderation or filtering systems where strings must be matched against restricted lists. Problems involving string matching and hash-based membership checks frequently use this exact design.
Recommended for interviews: The hash set lookup approach is what most interviewers expect. It demonstrates that you recognize repeated membership checks and optimize them with a hash-based structure. Mentioning the naive scan and then replacing it with a set shows clear reasoning. Implementing the early exit variant further shows attention to practical performance.
Approach 1: Approach 1: Hash Set for Fast Lookup
This approach uses a hash set to store the banned words. We then iterate through the message array, checking if each word appears in the set. We count the number of matches, and if it reaches two, we return true. Otherwise, we continue and return false if we check all words.
def is_spam(message, banned_words):
banned_set = set(banned_words)
match_count = 0
for word in message:
if word in banned_set:
match_count += 1
if match_count == 2:
return True
return False
if __name__ == "__main__":
message = ["hello", "world", "leetcode"]
banned_words = ["world", "hello"]
print(is_spam(message, banned_words))import java.util.HashSet;
import java.util.Set;
public class SpamChecker {
public static boolean isSpam(String[] message, String[] bannedWords) {
Set<String> bannedSet = new HashSet<>();
for (String word : bannedWords) {
bannedSet.add(word);
}
int matchCount = 0;
for (String word : message) {
if (bannedSet.contains(word)) {
matchCount++;
if (matchCount == 2) return true;
}
}
return false;
}
public static void main(String[] args) {
String[] message = {"hello", "world", "leetcode"};
String[] bannedWords = {"world", "hello"};
boolean isSpam = isSpam(message, bannedWords);
System.out.println(isSpam ? "true" : "false");
}
}#include <iostream>
#include <unordered_set>
#include <vector>
#include <string>
bool isSpam(const std::vector<std::string>& message, const std::vector<std::string>& bannedWords) {
std::unordered_set<std::string> bannedSet(bannedWords.begin(), bannedWords.end());
int matchCount = 0;
for (const auto& word : message) {
if (bannedSet.count(word)) {
matchCount++;
if (matchCount == 2) return true;
}
}
return false;
}
int main() {
std::vector<std::string> message = {"hello", "world", "leetcode"};
std::vector<std::string> bannedWords = {"world", "hello"};
bool result = isSpam(message, bannedWords);
std::cout << (result ? "true" : "false") << std::endl;
return 0;
}function isSpam(message, bannedWords) {
const bannedSet = new Set(bannedWords);
let matchCount = 0;
for (const word of message) {
if (bannedSet.has(word)) {
matchCount++;
if (matchCount === 2) return true;
}
}
return false;
}
const message = ['hello', 'world', 'leetcode'];
const bannedWords = ['world', 'hello'];
console.log(isSpam(message, bannedWords));#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdlib.h>
#define MAX_WORD_LENGTH 16
typedef struct HashSet {
char** words;
int size;
} HashSet;
HashSet* create_hash_set(int size) {
HashSet* set = (HashSet*) malloc(sizeof(HashSet));
set->words = (char**) calloc(size, sizeof(char*));
set->size = size;
return set;
}
void add_to_hash_set(HashSet* set, const char* word) {
int hash = 0;
int len = strlen(word);
for (int i = 0; i < len; i++) {
hash = (hash * 31 + word[i]) % set->size;
}
set->words[hash] = strdup(word);
}
bool is_in_hash_set(HashSet* set, const char* word) {
int hash = 0;
int len = strlen(word);
for (int i = 0; i < len; i++) {
hash = (hash * 31 + word[i]) % set->size;
}
return set->words[hash] && strcmp(set->words[hash], word) == 0;
}
bool isSpam(char** message, int messageSize, char** bannedWords, int bannedSize) {
HashSet* set = create_hash_set(bannedSize * 2);
for (int i = 0; i < bannedSize; i++) {
add_to_hash_set(set, bannedWords[i]);
}
int matchCount = 0;
for (int i = 0; i < messageSize; i++) {
if (is_in_hash_set(set, message[i])) {
matchCount++;
if (matchCount == 2) return true;
}
}
return false;
}
int main() {
char* message[] = {"hello", "world", "leetcode"};
char* bannedWords[] = {"world", "hello"};
bool result = isSpam(message, 3, bannedWords, 2);
printf("%s\n", result ? "true" : "false");
return 0;
}using System;
using System.Collections.Generic;
class Program {
public static bool IsSpam(string[] message, string[] bannedWords) {
HashSet<string> bannedSet = new HashSet<string>(bannedWords);
int matchCount = 0;
foreach (string word in message) {
if (bannedSet.Contains(word)) {
matchCount++;
if (matchCount == 2) return true;
}
}
return false;
}
static void Main() {
string[] message = {"hello", "world", "leetcode"};
string[] bannedWords = {"world", "hello"};
bool result = IsSpam(message, bannedWords);
Console.WriteLine(result ? "true" : "false");
}
}The Python solution uses a set for banned words. This allows for O(1) average time complexity for lookups. We iterate through the message, and once a counter reaches two due to matches, we return true.
Time complexity: O(n + m), where n is the length of the message and m is the size of the banned words list. Space complexity is O(m) for the set.
Approach 2: Approach 2: Frequency Count with Early Exit
To avoid extra space usage while maintaining efficiency, one can count occurrences of banned words directly within the message. Utilize a counter to track the number of times a banned word appears in the message array, exiting early when two are found.
def is_spam(message, banned_words):
match_count = 0
for word in message:
if word in banned_words:
match_count += 1
if match_count == 2:
return True
return False
if __name__ == "__main__":
message = ["hello", "world", "leetcode"]
banned_words = ["world", "hello"]
print(is_spam(message, banned_words))public class SpamCheckerBruteForce {
public static boolean isSpam(String[] message, String[] bannedWords) {
int matchCount = 0;
for (String word : message) {
for (String banned : bannedWords) {
if (word.equals(banned)) {
matchCount++;
if (matchCount == 2) return true;
}
}
}
return false;
}
public static void main(String[] args) {
String[] message = {"hello", "world", "leetcode"};
String[] bannedWords = {"world", "hello"};
boolean result = isSpam(message, bannedWords);
System.out.println(result ? "true" : "false");
}
}#include <iostream>
#include <vector>
#include <string>
bool isSpam(const std::vector<std::string>& message, const std::vector<std::string>& bannedWords) {
int matchCount = 0;
for (const auto& word : message) {
for (const auto& banned : bannedWords) {
if (word == banned) {
matchCount++;
if (matchCount == 2) return true;
}
}
}
return false;
}
int main() {
std::vector<std::string> message = {"hello", "world", "leetcode"};
std::vector<std::string> bannedWords = {"world", "hello"};
bool result = isSpam(message, bannedWords);
std::cout << (result ? "true" : "false") << std::endl;
return 0;
}function isSpam(message, bannedWords) {
let matchCount = 0;
for (const word of message) {
if (bannedWords.includes(word)) {
matchCount++;
if (matchCount === 2) return true;
}
}
return false;
}
const message = ['hello', 'world', 'leetcode'];
const bannedWords = ['world', 'hello'];
console.log(isSpam(message, bannedWords));#include <stdio.h>
#include <string.h>
#include <stdbool.h>
bool isSpam(char** message, int messageSize, char** bannedWords, int bannedSize) {
int matchCount = 0;
for (int i = 0; i < messageSize; i++) {
for (int j = 0; j < bannedSize; j++) {
if (strcmp(message[i], bannedWords[j]) == 0) {
matchCount++;
if (matchCount == 2) return true;
}
}
}
return false;
}
int main() {
char* message[] = {"hello", "world", "leetcode"};
char* bannedWords[] = {"world", "hello"};
bool result = isSpam(message, 3, bannedWords, 2);
printf("%s\n", result ? "true" : "false");
return 0;
}using System;
class SpamChecker {
public static bool IsSpam(string[] message, string[] bannedWords) {
int matchCount = 0;
foreach (string word in message) {
foreach (string banned in bannedWords) {
if (word == banned) {
matchCount++;
if (matchCount == 2) return true;
}
}
}
return false;
}
static void Main() {
string[] message = {"hello", "world", "leetcode"};
string[] bannedWords = {"world", "hello"};
bool isSpam = IsSpam(message, bannedWords);
Console.WriteLine(isSpam ? "true" : "false");
}
}This Python solution demonstrates a brute force strategy that compares each message word with each banned word using nested loops. While feasible with minimal memory use, performance may degrade with longer input lists.
Time complexity is O(n * m), where n and m correspond to the lengths of message and bannedWords. Space complexity is constant O(1).
Approach 3: Hash Table
We use a hash table s to store all the words in bannedWords. Then, we traverse each word in message. If the word appears in the hash table s, we increment the counter cnt by one. If cnt is greater than or equal to 2, we return true; otherwise, we return false.
The time complexity is O((n + m) times |w|), and the space complexity is O(m times |w|). Here, n is the length of the array message, and m and |w| are the length of the array bannedWords and the maximum length of the words in the array, respectively.
function reportSpam(message: string[], bannedWords: string[]): boolean {
const s = new Set<string>(bannedWords);
let cnt = 0;
for (const w of message) {
if (s.has(w) && ++cnt >= 2) {
return true;
}
}
return false;
}func reportSpam(message []string, bannedWords []string) bool {
s := map[string]bool{}
for _, w := range bannedWords {
s[w] = true
}
cnt := 0
for _, w := range message {
if s[w] {
cnt++
if cnt >= 2 {
return true
}
}
}
return false
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Hash Set for Fast Lookup | Time complexity: O(n + m), where n is the length of the message and m is the size of the banned words list. Space complexity is O(m) for the set. |
| Approach 2: Frequency Count with Early Exit | Time complexity is O(n * m), where n and m correspond to the lengths of message and bannedWords. Space complexity is constant O(1). |
| Hash Table | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Set for Fast Lookup | O(n + m) | O(m) | General case where repeated membership checks are needed |
| Frequency Count with Early Exit | O(n + m) | O(m) | When spam may appear early and early termination improves runtime |
Frequently asked questions
Is Report Spam Message easy or hard?
Report Spam Message is generally considered a medium-level problem. The logic is straightforward, but recognizing the need for a hash set to optimize repeated lookups is the key step that interviewers expect.
Report Spam Message Python/Java solution
In Python, the typical solution uses a set for banned words and iterates through the message array counting matches. Java and C++ implementations follow the same logic using HashSet or unordered_set. The algorithm remains O(n + m) across all languages.
How to solve Report Spam Message in O(n)?
Store all banned words in a hash set, then scan the message once. For each word, check membership in the set and increment a counter if it exists. As soon as the counter reaches two, return true. This single-pass strategy keeps the runtime linear.
What is the best approach for Report Spam Message?
The hash set lookup approach is the most efficient and commonly expected solution. Convert the banned word list into a set, then iterate through the message and count how many words appear in that set. Each lookup runs in O(1), giving an overall time complexity of O(n + m) with O(m) additional space.
Is Report Spam Message asked at Google/Amazon/Meta?
Problems involving hash sets and fast membership checks appear frequently in interviews at companies like Amazon, Google, and Meta. While the exact problem may vary, the pattern of converting a list into a hash set for O(1) lookups is a common interview expectation.
What data structure is used in Report Spam Message?
A hash set (or hash map) is the primary data structure used. It allows constant-time checks to determine whether a message word exists in the banned list. This drastically improves performance compared to repeatedly scanning the banned array.
What is the time complexity of Report Spam Message?
The optimal solution runs in O(n + m) time, where n is the number of words in the message and m is the number of banned words. Building the hash set takes O(m) and scanning the message takes O(n). Space complexity is O(m) for storing the banned words.