Report Spam Message

Medium
1820.

Report Spam Message

Report Spam Message is a medium coding problem on arrays, strings and hash table, asked in Amazon and Google interviews.

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^5
  • 1 <= message[i].length, bannedWords[i].length <= 15
  • message[i] and bannedWords[i] consist only of lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} message
 * @param {string[]} bannedWords
 * @return {boolean}
 */
var reportSpam = function(message, bannedWords) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^5
  • 1 <= message[i].length, bannedWords[i].length <= 15
  • message[i] and bannedWords[i] consist only of lowercase English letters

Hints for Report Spam Message

  1. Hint 1

    For every word of the message you need to answer one question: is it in the banned list?

  2. Hint 2

    Scanning bannedWords for each word is O(n * m) — too slow at 10^5 each. Put the banned words in a hash set first.

  3. 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

  1. Insert every word of bannedWords into a hash set.
  2. Walk message, incrementing a counter whenever the word is in the set.
  3. Return true as soon as the counter reaches 2; return false if 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 — prizes does not match prize.

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 False

Java

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.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings