Report Spam Message — Solution in Python, Java & C++
Report Spam Message solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Report Spam Message is a medium coding problem on arrays, strings and hash table, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Strings, Hash Table
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A message arrives as an array of words message, and a moderation list holds the words in bannedWords.
The message is spam if at least two of its words (counted by position, so the same banned word appearing twice counts twice) are exactly equal to some word in bannedWords.
Return true if the message is spam, and false otherwise.
Example 1
Input: message = ["free","prize","click","now"], bannedWords = ["prize","now"]
Output: true
Explanation: `prize` and `now` are both banned.
Example 2
Input: message = ["hello","coder","free","code"], bannedWords = ["free","spam"]
Output: false
Explanation: Only `free` is banned — one match is not enough.
Example 3
Input: message = ["win","win"], bannedWords = ["win"]
Output: true
Explanation: The same banned word appearing twice gives two matching words.
Constraints
1 <= message.length, bannedWords.length <= 10^51 <= message[i].length, bannedWords[i].length <= 15message[i] and bannedWords[i] consist only of lowercase English letters
Hints for Report Spam Message
Hint 1
For every word of the message you need to answer one question: is it in the banned list?
Hint 2
Scanning
bannedWordsfor each word isO(n * m)— too slow at10^5each. Put the banned words in a hash set first.Hint 3
Count the message words found in the set and stop as soon as the count reaches two.
How to solve Report Spam Message
Membership tests against a fixed list are what a hash set is for: build it once from bannedWords, then each message word is checked in expected constant time.
Approach
- Insert every word of
bannedWordsinto a hash set. - Walk
message, incrementing a counter whenever the word is in the set. - Return
trueas soon as the counter reaches 2; returnfalseif the walk ends first.
Why it works
The definition counts message positions whose word is banned, so a single pass with an exact-match lookup counts exactly those positions. Duplicates in bannedWords do not matter because the set only records membership, and duplicates in message count separately because each position is visited once.
Complexity
- Time —
O((n + m) * L) where L ≤ 15 is the word length - Space —
O(m * L)
Pitfalls
- Counting distinct banned words found is wrong:
["win","win"]with["win"]is spam. - Matches must be whole words —
prizesdoes not matchprize.
Reference solution
Python
from typing import List
def reportSpam(message: List[str], bannedWords: List[str]) -> bool:
banned = set(bannedWords)
hits = 0
for word in message:
if word in banned:
hits += 1
if hits >= 2:
return True
return FalseJava
public static boolean reportSpam(String[] message, String[] bannedWords) {
Set<String> banned = new HashSet<>(Arrays.asList(bannedWords));
int hits = 0;
for (String w : message) {
if (banned.contains(w) && ++hits >= 2) return true;
}
return false;
}C++
bool reportSpam(vector<string>& message, vector<string>& bannedWords) {
unordered_set<string> banned(bannedWords.begin(), bannedWords.end());
int hits = 0;
for (const string& w : message) {
if (banned.count(w) && ++hits >= 2) return true;
}
return false;
}JavaScript
var reportSpam = function(message, bannedWords) {
var banned = new Set(bannedWords);
var hits = 0;
for (var i = 0; i < message.length; i++) {
if (banned.has(message[i])) {
hits++;
if (hits >= 2) return true;
}
}
return false;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.