# Report Spam Message
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/report-spam-message)
Canonical: https://scaleengineer.com/dsa/problems/report-spam-message
**Data structures:** Array, Hash Table, String
---
## 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 <= 105`
* `1 <= message[i].length, bannedWords[i].length <= 15`
* `message[i]` and `bannedWords[i]` consist only of lowercase English letters.

# Approaches
## Brute Force using Nested Loops
This approach directly translates the problem statement into code. We iterate through each word in the `message` and, for each word, we iterate through the entire `bannedWords` array to check for a match. A counter keeps track of how many banned words have been found in the message.
**Time:** O(N * M * L), where N is the number of words in `message`, M is the number of words in `bannedWords`, and L is the maximum length of a word. For each of the N words in `message`, we iterate through all M words in `bannedWords`. String comparison takes O(L) time. This approach is too slow for the given constraints. · **Space:** O(1), as we only use a few variables to store the count and loop indices, not dependent on the input size.
**Pros:** Simple to understand and implement.; Requires no extra space, making it very memory-efficient.
**Cons:** Extremely inefficient for large inputs due to the O(N*M) complexity of the nested loops.; Will likely cause a 'Time Limit Exceeded' (TLE) error on platforms with strict time constraints.
### Explanation
This method involves a straightforward, nested-loop comparison. We take each word from the `message` and compare it against every single word in the `bannedWords` list. We use a counter to track the number of matches found. If the count of banned words found in the message reaches two, we can immediately conclude the message is spam and return `true`. If we iterate through the entire message without the count reaching two, the message is not spam.

```java
class Solution {
    public boolean isSpam(String[] message, String[] bannedWords) {
        int bannedCount = 0;
        for (String word : message) {
            for (String bannedWord : bannedWords) {
                if (word.equals(bannedWord)) {
                    bannedCount++;
                    // Once a word is identified as banned,
                    // we can break the inner loop and check the next word in the message.
                    break; 
                }
            }
            // Early exit if we've already found two banned words.
            if (bannedCount >= 2) {
                return true;
            }
        }
        return false;
    }
}
```
### Algorithm
*   Initialize a counter, `bannedCount`, to zero.
*   Iterate through each `word` in the `message` array.
*   For each `word`, start a nested loop to iterate through every `bannedWord` in the `bannedWords` array.
*   Inside the nested loop, compare the current `word` from the message with the current `bannedWord`.
*   If they are an exact match, increment `bannedCount` and break the inner loop to move to the next word in `message`.
*   After the inner loop, check if `bannedCount` has reached 2. If it has, the condition for spam is met, so return `true` immediately.
*   If the outer loop finishes and `bannedCount` is less than 2, return `false`.

## Optimized Approach using a Hash Set
To improve upon the brute-force approach, we can optimize the process of checking if a word is banned. Instead of repeatedly scanning the `bannedWords` array, we can first store all banned words in a data structure that provides fast lookups, such as a Hash Set. This pre-processing step allows us to check if a word is banned in nearly constant time on average.
**Time:** O((N + M) * L), where N is the length of `message`, M is the length of `bannedWords`, and L is the maximum word length. It takes O(M * L) to build the hash set and O(N * L) to iterate through the message and perform lookups. This is efficient enough to pass the given constraints. · **Space:** O(M * L), where M is the number of words in `bannedWords` and L is their maximum length. This space is required to store the banned words in the hash set.
**Pros:** Highly efficient time complexity, suitable for large inputs.; The standard and most practical solution for this type of 'existence check' problem.
**Cons:** Uses extra space proportional to the number and length of banned words.
### Explanation
This optimized solution avoids the costly repeated search through the `bannedWords` array. By first populating a `HashSet` with all the banned words, we create a quick-reference dictionary. Checking if a word is in this set is, on average, a constant-time operation. We then iterate through the `message` just once, checking each word against our set. We keep a count of the banned words found, and as soon as the count hits two, we return `true`. This pre-computation step dramatically reduces the overall time complexity.

```java
import java.util.HashSet;
import java.util.Set;
import java.util.Arrays;

class Solution {
    public boolean isSpam(String[] message, String[] bannedWords) {
        // Step 1: Add all banned words to a HashSet for O(1) average time lookups.
        Set<String> bannedSet = new HashSet<>(Arrays.asList(bannedWords));

        // Step 2: Iterate through the message and count banned words.
        int bannedCount = 0;
        for (String word : message) {
            if (bannedSet.contains(word)) {
                bannedCount++;
            }
            
            // Step 3: If the count reaches 2, it's spam. Return true immediately.
            if (bannedCount >= 2) {
                return true;
            }
        }

        // If the loop finishes, the message is not spam.
        return false;
    }
}
```
### Algorithm
*   Create a `HashSet<String>` to store the banned words for efficient lookup.
*   Iterate through the `bannedWords` array and add every word to the hash set.
*   Initialize a counter `bannedCount` to 0.
*   Iterate through each `word` in the `message` array.
*   For each `word`, use the hash set's `contains` method to check if it is a banned word.
*   If the word is found in the set, increment `bannedCount`.
*   If `bannedCount` reaches 2, we have found at least two banned words. Return `true` immediately.
*   If the loop completes and `bannedCount` is still less than 2, return `false`.

# Solutions
### Java

```java
class Solution { public boolean reportSpam ( String [] message , String [] bannedWords ) { Set < String > s = new HashSet <>(); for ( var w : bannedWords ) { s . add ( w ); } int cnt = 0 ; for ( var w : message ) { if ( s . contains ( w ) && ++ cnt >= 2 ) { return true ; } } return false ; } }
```

### CPP

```cpp
class Solution { public: bool reportSpam ( vector < string >& message , vector < string >& bannedWords ) { unordered_set < string > s ( bannedWords . begin (), bannedWords . end ()); int cnt = 0 ; for ( const auto & w : message ) { if ( s . contains ( w ) && ++ cnt >= 2 ) { return true ; } } return false ; } };
```

### Python

```python
class Solution : def reportSpam ( self , message : List [ str ], bannedWords : List [ str ]) -> bool : s = set ( bannedWords ) return sum ( w in s for w in message ) >= 2
```