# Count Common Words With One Occurrence
**Difficulty:** EASY
[External](https://leetcode.com/problems/count-common-words-with-one-occurrence)
Canonical: https://scaleengineer.com/dsa/problems/count-common-words-with-one-occurrence
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Array, Hash Table, String
**Companies:** [Jane Street](https://scaleengineer.com/companies/jane-street)
---
## Problem
Given two string arrays `words1` and `words2`, return _the number of strings that appear **exactly once** in **each** of the two arrays._

**Example 1:**

**Input:** words1 = ["leetcode","is","amazing","as","is"], words2 = ["amazing","leetcode","is"]
**Output:** 2
**Explanation:**
- "leetcode" appears exactly once in each of the two arrays. We count this string.
- "amazing" appears exactly once in each of the two arrays. We count this string.
- "is" appears in each of the two arrays, but there are 2 occurrences of it in words1. We do not count this string.
- "as" appears once in words1, but does not appear in words2. We do not count this string.
Thus, there are 2 strings that appear exactly once in each of the two arrays.

**Example 2:**

**Input:** words1 = ["b","bb","bbb"], words2 = ["a","aa","aaa"]
**Output:** 0
**Explanation:** There are no strings that appear in each of the two arrays.

**Example 3:**

**Input:** words1 = ["a","ab"], words2 = ["a","a","a","ab"]
**Output:** 1
**Explanation:** The only string that appears exactly once in each of the two arrays is "ab".

**Constraints:**

* `1 <= words1.length, words2.length <= 1000`
* `1 <= words1[i].length, words2[j].length <= 30`
* `words1[i]` and `words2[j]` consists only of lowercase English letters.

# Approaches
## Brute Force with Nested Loops
This approach iterates through each unique word in the first array, `words1`. For each word, it then performs two separate counts: one to find its frequency within `words1` and another to find its frequency within `words2`. If both frequencies are exactly one, a counter is incremented. To avoid redundant checks for duplicate words within `words1`, a `HashSet` is used to keep track of words that have already been processed.
**Time:** O(N * (N*L + M*L)), where N is the length of `words1`, M is the length of `words2`, and L is the maximum length of a word. For each of the (at most) N unique words in `words1`, we iterate through `words1` (cost `N*L`) and `words2` (cost `M*L`). This quadratic complexity makes it very slow for larger inputs. · **Space:** O(U * L), where U is the number of unique words in `words1` and L is the maximum length of a word. This space is used by the `processed` set. In the worst case, U can be N (the total number of words in `words1`), making the space complexity O(N * L).
**Pros:** Simple to understand and implement without requiring knowledge of more complex data structures.; Uses a relatively small amount of extra space if the number of unique words is low.
**Cons:** Extremely inefficient due to nested loops, leading to a high time complexity.; Performs redundant computations by repeatedly scanning the arrays.; Likely to result in a 'Time Limit Exceeded' error on larger test cases.
### Explanation
The brute-force method directly translates the problem's conditions into nested loops. We iterate through each word in the first list, `words1`. To ensure we only consider each unique word once, we use a `Set` to keep track of words we've already analyzed. For a given word, we first count its occurrences in `words1`. If the count isn't one, we move on. If it is one, we then proceed to count its occurrences in `words2`. If that count is also one, we've found a word that satisfies the condition, and we increment our result counter.

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

class Solution {
    public int countWords(String[] words1, String[] words2) {
        int commonCount = 0;
        Set<String> processed = new HashSet<>();
        for (String word1 : words1) {
            if (processed.contains(word1)) {
                continue;
            }
            processed.add(word1);

            int count1 = 0;
            for (String w : words1) {
                if (w.equals(word1)) {
                    count1++;
                }
            }

            if (count1 == 1) {
                int count2 = 0;
                for (String w : words2) {
                    if (w.equals(word1)) {
                        count2++;
                    }
                }
                if (count2 == 1) {
                    commonCount++;
                }
            }
        }
        return commonCount;
    }
}
```
### Algorithm
- Initialize a counter `commonCount` to 0.
- Create a `HashSet` called `processed` to store words from `words1` that have already been checked to avoid redundant work.
- Loop through each `word` in `words1`:
  - If `word` is already in `processed`, skip to the next iteration.
  - Add `word` to the `processed` set.
  - Initialize `count1 = 0` to count the frequency of `word` in `words1`.
  - Loop through `words1` again to count occurrences of `word` and update `count1`.
  - If `count1` is exactly 1, then proceed to check in `words2`.
  - Initialize `count2 = 0` to count the frequency of `word` in `words2`.
  - Loop through `words2` to count occurrences of `word` and update `count2`.
  - If `count2` is also exactly 1, it means the word appears once in both arrays. Increment `commonCount`.
- After the loops complete, return `commonCount`.

## Using Two Hash Maps for Frequency Counting
A much more efficient approach involves using hash maps to pre-calculate the frequency of each word in both arrays. We can use one hash map for `words1` and another for `words2`. After populating both maps, we iterate through one of the maps and check if the corresponding word meets the criteria (frequency of 1) in both maps.
**Time:** O(N*L + M*L), where N is the length of `words1`, M is the length of `words2`, and L is the maximum length of a word. Populating the first map takes O(N*L), the second map takes O(M*L), and the final iteration takes O(U1*L) where U1 is the number of unique words in `words1`. The overall complexity is linear with respect to the total number of characters in both arrays. · **Space:** O(U1*L + U2*L), where U1 and U2 are the number of unique words in `words1` and `words2` respectively, and L is the maximum word length. This space is required to store the words and their counts in the two hash maps.
**Pros:** Significantly faster than the brute-force approach with a linear time complexity.; Efficiently handles large inputs without timing out.; The logic is clean and directly models the problem of counting and checking frequencies.
**Cons:** Uses extra space to store two hash maps, which can be significant if the number of unique words is very large.
### Explanation
This optimized approach avoids the costly repeated scanning of the input arrays by pre-processing them. We first create a hash map to store the frequency of each word in `words1`. Then, we do the same for `words2` with a second hash map. This allows us to determine the frequency of any word in O(1) average time. 

Once both frequency maps are built, we can iterate through the keys of the first map. For each word, we check if its count is 1 in the first map and also 1 in the second map. If a word satisfies both conditions, we increment our final counter.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int countWords(String[] words1, String[] words2) {
        Map<String, Integer> freq1 = new HashMap<>();
        for (String word : words1) {
            freq1.put(word, freq1.getOrDefault(word, 0) + 1);
        }

        Map<String, Integer> freq2 = new HashMap<>();
        for (String word : words2) {
            freq2.put(word, freq2.getOrDefault(word, 0) + 1);
        }

        int count = 0;
        for (String word : freq1.keySet()) {
            if (freq1.get(word) == 1 && freq2.getOrDefault(word, 0) == 1) {
                count++;
            }
        }
        return count;
    }
}
```
### Algorithm
- Create a `HashMap<String, Integer>` named `freqMap1`.
- Iterate through `words1`. For each `word`, update its count in `freqMap1`.
- Create a second `HashMap<String, Integer>` named `freqMap2`.
- Iterate through `words2`. For each `word`, update its count in `freqMap2`.
- Initialize a counter `commonCount` to 0.
- Iterate through the keys (words) in `freqMap1`.
- For each `word`:
  - Check if its frequency in `freqMap1` is 1.
  - Check if the same `word` exists in `freqMap2` and its frequency there is also 1.
  - If both conditions are true, increment `commonCount`.
- Return `commonCount`.

# Solutions
### Java

```java
class Solution {
public
  int countWords(String[] words1, String[] words2) {
    Map<String, Integer> cnt1 = new HashMap<>();
    Map<String, Integer> cnt2 = new HashMap<>();
    for (var w : words1) {
      cnt1.merge(w, 1, Integer : : sum);
    }
    for (var w : words2) {
      cnt2.merge(w, 1, Integer : : sum);
    }
    int ans = 0;
    for (var e : cnt1.entrySet()) {
      if (e.getValue() == 1 && cnt2.getOrDefault(e.getKey(), 0) == 1) {
        ++ans;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int countWords(vector<string> &words1, vector<string> &words2) {
    unordered_map<string, int> cnt1;
    unordered_map<string, int> cnt2;
    for (auto &w : words1) {
      ++cnt1[w];
    }
    for (auto &w : words2) {
      ++cnt2[w];
    }
    int ans = 0;
    for (auto &[w, v] : cnt1) {
      ans += v == 1 && cnt2[w] == 1;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def countWords(self, words1: List[str], words2: List[str]) -> int: cnt1 = Counter(words1) cnt2 = Counter(words2) return sum(v == 1 and cnt2[w] == 1 for w, v in cnt1 . items())

```