#2085

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Count Common Words With One Occurrence

Learn how to efficiently count strings appearing exactly once in both arrays using array scanning and hash lookup patterns.

array hash table string counting

Problem Statement

Given two string arrays words1 and words2, determine how many strings appear exactly once in each array. Return this count as an integer.

For example, if words1 contains ["leetcode","is","amazing","as","is"] and words2 contains ["amazing","leetcode","is"], only "leetcode" and "amazing" appear exactly once in both arrays, so the result is 2.

Examples

Example 1

Input: words1 = ["leetcode","is","amazing","as","is"], words2 = ["amazing","leetcode","is"]

Output: 2

"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

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

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.

Solution Approach

Count Frequencies with Hash Maps

Use two hash maps to record the frequency of each string in words1 and words2. This allows constant-time lookup when verifying if a string occurs exactly once in both arrays.

Scan First Array

Iterate through words1, incrementing counts in the first hash map. This identifies duplicates early and ensures only candidates appearing once move to final counting.

Check Second Array and Count Matches

Iterate through words2, updating the second hash map. Then, for each string in the first map with count one, check if its count in the second map is also one. Sum all such matches to get the answer.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n + m) where n and m are the lengths of words1 and words2, since each array is scanned once and hash lookups are constant time. Space complexity is O(n + m) for storing frequency counts in hash maps.

What Interviewers Usually Probe

Are you tracking frequency efficiently without nested loops?
Did you consider strings that appear more than once in one array?
Can you achieve linear time using hash tables for this problem?

Common Pitfalls or Variants

Common pitfalls

Counting strings that appear multiple times in one array.
Using nested loops instead of hash maps, increasing time complexity.
Forgetting to check both arrays for exactly one occurrence.

Follow-up variants

Count strings appearing at least once in both arrays instead of exactly once.
Count strings appearing exactly k times in both arrays.
Return the list of strings that satisfy the one-occurrence condition instead of just the count.

FAQ

What pattern does 'Count Common Words With One Occurrence' follow?

It follows the array scanning plus hash lookup pattern, using hash maps to track word frequency efficiently.

Can this solution handle arrays with duplicate strings?

Yes, the solution ensures only strings with exactly one occurrence in each array are counted.

What is the time complexity for this problem?

Time complexity is O(n + m) since each array is scanned once and hash table operations are constant time.

Does the order of words in arrays matter?

No, order does not matter because hash maps track frequency independently of position.

Can this approach be extended to more than two arrays?

Yes, by maintaining separate frequency maps for each array and counting words appearing exactly once in all arrays.

terminal

Solution

Solution 1: Hash Table + Counting

We can use two hash tables, $cnt1$ and $cnt2$, to count the occurrences of each string in the two string arrays respectively. Then, we traverse one of the hash tables. If a string appears once in the other hash table and also appears once in the current hash table, we increment the answer by one.

1

2

3

4

5

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())

Continue Practicing

#2053 kth distinct string in an array #2131 longest palindrome by concatenating two letter words #2023 number of pairs of strings with concatenation equal to target