Count Common Words With One Occurrence - Solution & Explanation
Problem Statement
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 <= 10001 <= words1[i].length, words2[j].length <= 30words1[i]andwords2[j]consists only of lowercase English letters.
Approach Overview
Problem Overview: You receive two string arrays. A word should be counted only if it appears exactly once in both arrays. The task is to compute how many such words exist.
Approach 1: Using Frequency Counters (O(n + m) time, O(n + m) space)
The most direct solution uses two frequency maps. Iterate through words1 and words2 and store the number of occurrences of each word using a hash map. After building both maps, iterate through the keys of the first map and check two conditions: the word appears exactly once in the first array and exactly once in the second array. Each lookup in a hash map runs in constant time on average, so the full pass stays linear.
This approach relies on a hash table for fast counting and lookup. The logic is easy to reason about and mirrors how you would manually count occurrences. Because every word is processed once while building the frequency tables, the total runtime is O(n + m), where n and m are the lengths of the two arrays. The space complexity is also O(n + m) since the maps store counts for all distinct words. This is the most common implementation used in production and interviews.
Approach 2: Simultaneous Counting with Sets (O(n + m) time, O(n + m) space)
An alternative method tracks unique and repeated words while iterating. Use two sets for each array: one for words seen exactly once and another for words that appear more than once. As you iterate through each array, insert unseen words into the "seen once" set. If the word appears again, move it to the duplicate set. After processing both arrays, iterate through the unique set of the first array and check whether the word also appears in the unique set of the second array.
This approach uses string comparisons and hash-based set membership checks to maintain constant-time operations. It avoids explicit numeric counters and instead tracks uniqueness directly through set membership. Runtime remains O(n + m) because each word triggers at most a few constant-time set operations. Space complexity is O(n + m) due to the sets storing unique and duplicate entries.
Recommended for interviews: The frequency counter approach is what most interviewers expect. It clearly demonstrates understanding of array traversal and hash-based counting. The set-based approach is also valid and shows you understand how to track uniqueness efficiently, but the hash map counting pattern is the most recognizable solution pattern for this problem.
Approach 1: Approach 1: Using Frequency Counters
In this approach, we use hash maps (dictionaries) to count the occurrences of each word in both arrays. Then, we iterate through the words in one of the arrays and check if the occurrences of that word are exactly one in both hash maps.
This C solution uses a simple custom hash map to count occurrences of each word in the two arrays. The function `find_or_insert` checks for a word in the map or inserts it if not present, allowing word counts to be accumulated separately for each array. Finally, it iterates to count words appearing exactly once in both arrays.
Complexity
Time Complexity: O(n + m) where n and m are the lengths of words1 and words2 respectively.
Space Complexity: O(u) where u is the number of unique words across both arrays.
Approach 2: Approach 2: Simultaneous Counting with Sets
This approach leverages sets to track which words should be counted as appearing exactly once. First, we use counters to count the occurrences. Then, using the sets, we determine whether a word meets the condition of appearing once in both arrays.
This C solution uses arrays of strings to keep track of unique and duplicate words separately. The algorithm processes words to partition them into unique and duplicate sets, preventing miscounts.
Complexity
Time Complexity: O(n * m) (due to '<' contains' instead of hash)
Space Complexity: O(n + m) where n and m are effective counts for unique and duplicate sets.
Approach 3: 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.
The time complexity is O(n + m), and the space complexity is O(n + m). Where n and m are the lengths of the two string arrays respectively.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Using Frequency Counters | Time Complexity: O(n + m) where n and m are the lengths of words1 and words2 respectively. |
| Approach 2: Simultaneous Counting with Sets | Time Complexity: O(n * m) (due to '<' contains' instead of hash) |
| Hash Table + Counting | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Frequency Counters with Hash Map | O(n + m) | O(n + m) | General case. Most readable and commonly expected interview solution. |
| Simultaneous Counting with Sets | O(n + m) | O(n + m) | When tracking unique vs duplicate words directly without numeric counters. |
Video Solution
Leetcode | 2085. Count Common Words With One Occurrence | Easy | Java Solution • Developer Docs • 1,340 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Count Common Words With One Occurrence easy or hard?
Count Common Words With One Occurrence Python/Java solution
How to solve Count Common Words With One Occurrence in O(n)?
What is the best approach for Count Common Words With One Occurrence?
Is Count Common Words With One Occurrence asked at Google/Amazon/Meta?
What data structure is used in Count Common Words With One Occurrence?
What is the time complexity of Count Common Words With One Occurrence?
Ready to solve this problem?
Practice Count Common Words With One Occurrence with our built-in code editor and test cases.
Practice on FleetCode