Count Common Words With One Occurrence

Difficulty: Easy | Acceptance: 73.40% | Paid: No Topics: Array, Hash Table, String, Counting

Given two 0-indexed string arrays words1 and words2, return the number of strings that appear exactly once in each of the two arrays.

• Examples
• Constraints
• Brute Force
• Hash Map Frequency Count
• Set Intersection

Examples

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.
- "amazing" appears exactly once in each of the two arrays.
- "is" appears in both arrays, but there are 2 occurrences of "is" in words1 and 1 occurrence in words2.

Example 2:

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

Example 3:

Input: words1 = ["a","ab"], words2 = ["a","a","a","ab"]
Output: 1
Explanation:
- "ab" appears exactly once in each of the two arrays.
- "a" appears 3 times in words2, so it does not meet the condition.

Constraints

1 <= words1.length, words2.length <= 10³
1 <= words1[i].length, words2[j].length <= 30
words1[i] and words2[j] consist only of lowercase English letters.

Brute Force

Intuition Iterate through every word in the first array and manually count its occurrences in both arrays to check if it appears exactly once in each.

Steps

• Initialize a result counter to 0.
• Iterate through each word in words1.
• For each word, count how many times it appears in words1.
• If the count is not exactly 1, skip to the next word.
• If the count is 1, count how many times it appears in words2.
• If the count in words2 is also exactly 1, increment the result counter.
• Return the result counter.

class Solution:
    def countWords(self, words1: List[str], words2: List[str]) -> int:
        count = 0
        for w in words1:
            if words1.count(w) == 1 and words2.count(w) == 1:
                count += 1
        return count

Complexity

• Time: O(n * (n + m)) where n is the length of words1 and m is the length of words2. For each word, we scan the arrays.
• Space: O(1)
• Notes: This approach is inefficient for large inputs but works for the given constraints (10³).

Hash Map Frequency Count

Intuition Use hash maps to store the frequency of every word in both arrays. Then iterate through the keys of one map to check if the frequency is 1 in both maps.

Steps

• Create a hash map freq1 to store word counts for words1.
• Create a hash map freq2 to store word counts for words2.
• Iterate through words1 and populate freq1.
• Iterate through words2 and populate freq2.
• Initialize a result counter to 0.
• Iterate through the keys of freq1.
• For each key, if its value in freq1 is 1 and its value in freq2 is 1, increment the result counter.
• Return the result counter.

from collections import Counter

class Solution:
    def countWords(self, words1: List[str], words2: List[str]) -> int:
        freq1 = Counter(words1)
        freq2 = Counter(words2)
        
        count = 0
        for w in freq1:
            if freq1[w] == 1 and freq2.get(w, 0) == 1:
                count += 1
        return count

Complexity

• Time: O(n + m) where n is the length of words1 and m is the length of words2. We iterate through both arrays once to build maps and then iterate through the keys of one map.
• Space: O(n + m) to store the frequency maps.
• Notes: This is the standard optimal approach for counting problems.

Set Intersection

Intuition We only care about words that appear exactly once. We can create sets containing only the words that appear exactly once in each array, then find the intersection of these two sets.

Steps

• Create a helper function getOnceOccurring(words) that returns a set of words appearing exactly once.
• Inside the helper, use a hash map to count frequencies.
• Iterate through the map and add keys with value 1 to a set.
• Call this helper for words1 to get set1.
• Call this helper for words2 to get set2.
• Iterate through set1 and check if each element exists in set2. Count the matches.
• Return the count.

from collections import Counter

class Solution:
    def countWords(self, words1: List[str], words2: List[str]) -> int:
        def getOnce(words):
            freq = Counter(words)
            return {w for w, c in freq.items() if c == 1}
        
        set1 = getOnce(words1)
        set2 = getOnce(words2)
        
        return len(set1 & set2)

Complexity

• Time: O(n + m) to build the frequency maps and sets.
• Space: O(n + m) to store the sets.
• Notes: This approach is conceptually clean, separating the filtering logic from the intersection logic.