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] and words2[j] consists only of lowercase English letters.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.
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.
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.
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.
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.
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.
Python
Java
C++
Go
TypeScript
| 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 | — |
| 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. |
Leetcode | 2085. Count Common Words With One Occurrence | Easy | Java Solution • Developer Docs • 1,262 views views
Watch 9 more video solutions →Practice Count Common Words With One Occurrence with our built-in code editor and test cases.
Practice on FleetCode