Problem Description

You are given two string arrays words1 and words2. Your task is to count how many strings appear exactly once in words1 AND also appear exactly once in words2.

In other words, you need to find strings that:

• Occur exactly 1 time in words1
• AND occur exactly 1 time in words2

The solution uses two hash tables (Counter objects) to count the frequency of each string in both arrays. cnt1 stores the count of strings in words1, and cnt2 stores the count of strings in words2.

The key logic is in the final line: for each word w in cnt1, we check if its count v equals 1 (appears once in words1) AND if cnt2[w] also equals 1 (appears once in words2). The sum() function counts how many words satisfy both conditions.

For example:

• If words1 = ["a", "b", "c", "a"] and words2 = ["b", "c", "c"]
• "a" appears 2 times in words1 (not exactly once) - doesn't count
• "b" appears 1 time in words1 and 1 time in words2 - counts
• "c" appears 1 time in words1 but 2 times in words2 - doesn't count
• Result: 1 (only "b" satisfies the condition)

Intuition

The problem asks us to find strings that are "unique" in both arrays - appearing exactly once in each. The natural approach is to count the frequency of each string in both arrays separately.

Why use hash tables? When we need to track occurrences of elements, hash tables provide an efficient way to store and retrieve counts. Python's Counter is perfect for this - it automatically counts the frequency of each element in a collection.

The key insight is that we need to check two conditions simultaneously:

1. A string appears exactly once in words1
2. The same string appears exactly once in words2

Instead of trying to find common elements first and then check their counts, we can be more efficient. We iterate through all words in the first hash table and for each word, check if it meets both conditions. This avoids creating intermediate data structures.

The elegance of the solution comes from the fact that cnt2[w] returns 0 if word w doesn't exist in words2. So when we check cnt2[w] == 1, it automatically handles both requirements: the word must exist in words2 AND appear exactly once. Words that don't exist in words2 will have a count of 0, failing the condition.

This approach has optimal time complexity O(n + m) where n and m are the lengths of the two arrays, as we only need to traverse each array once to build the counters, and then traverse one counter to check conditions.

Solution Approach

The implementation uses hash tables and counting to efficiently solve this problem. Here's how the solution works step by step:

Step 1: Count frequencies in both arrays

cnt1 = Counter(words1)
cnt2 = Counter(words2)

We create two Counter objects (hash tables) to store the frequency of each string. For example, if words1 = ["a", "b", "a"], then cnt1 = {"a": 2, "b": 1}.

Step 2: Iterate and check conditions

sum(v == 1 and cnt2[w] == 1 for w, v in cnt1.items())

This line does multiple things:

• cnt1.items() gives us pairs of (word, count) from the first array
• For each pair (w, v):
  • v == 1 checks if the word appears exactly once in words1
  • cnt2[w] == 1 checks if the same word appears exactly once in words2
  • The and operator ensures both conditions must be true
• The generator expression produces True (1) or False (0) for each word
• sum() counts how many True values we have, giving us the final answer

Why this approach is efficient:

• We only traverse each array once to build the counters: O(n) for words1 and O(m) for words2
• We then traverse cnt1 once to check conditions: O(unique words in words1)
• Each lookup in cnt2 is O(1) due to hash table implementation
• Overall time complexity: O(n + m) where n and m are the lengths of the two arrays
• Space complexity: O(n + m) for storing the two hash tables

The beauty of this solution lies in its simplicity - by using Counter objects, we avoid manually tracking frequencies and can directly query counts with clean, readable code.

Example Walkthrough

Let's walk through a concrete example to understand how the solution works.

Given:

• words1 = ["apple", "banana", "apple", "orange"]
• words2 = ["banana", "orange", "orange", "grape"]

Step 1: Build frequency counters

First, we count how many times each word appears in both arrays:

cnt1 = Counter(words1)
# cnt1 = {"apple": 2, "banana": 1, "orange": 1}

cnt2 = Counter(words2)  
# cnt2 = {"banana": 1, "orange": 2, "grape": 1}

Step 2: Check each word in cnt1

Now we iterate through each word in cnt1 and check if it meets both conditions:

• "apple": Appears 2 times in words1 (not exactly once), so it doesn't qualify
• "banana": Appears exactly once in words1 AND exactly once in words2 - this counts!
• "orange": Appears exactly once in words1 but twice in words2, so it doesn't qualify
• "grape": Only exists in words2, so it's not checked (we only iterate through cnt1)

Step 3: Count qualifying words

The expression sum(v == 1 and cnt2[w] == 1 for w, v in cnt1.items()) evaluates to:

• "apple": False and False = False (contributes 0)
• "banana": True and True = True (contributes 1)
• "orange": True and False = False (contributes 0)

Result: 0 + 1 + 0 = 1

Therefore, only 1 string ("banana") appears exactly once in both arrays.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n + m)

The time complexity breaks down as follows:

• Creating cnt1 using Counter(words1) takes O(n) time, where n is the length of words1
• Creating cnt2 using Counter(words2) takes O(m) time, where m is the length of words2
• The generator expression iterates through all items in cnt1, which contains at most n unique words, taking O(n) time
• For each word w in the iteration, accessing cnt2[w] takes O(1) time on average for hash table lookup
• The sum() function processes the generator expression in O(n) time

Total time complexity: O(n) + O(m) + O(n) = O(n + m)

Space Complexity: O(n + m)

The space complexity breaks down as follows:

• cnt1 stores at most n unique words and their counts, requiring O(n) space
• cnt2 stores at most m unique words and their counts, requiring O(m) space
• The generator expression and sum operation use O(1) additional space

Total space complexity: O(n) + O(m) = O(n + m)

Where n and m are the lengths of the arrays words1 and words2 respectively.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Checking Words Not Present in Both Arrays

The Problem: A common mistake is forgetting that when you access word_count_2[word] for a word that doesn't exist in words2, Python's Counter returns 0 (not an error). While this actually works correctly for our problem (since 0 ≠ 1), developers might misunderstand the logic or try to "optimize" by checking existence first.

Incorrect attempt:

# Unnecessarily checking if word exists first
result = sum(
    count == 1 and word in word_count_2 and word_count_2[word] == 1 
    for word, count in word_count_1.items()
)

Why it's a pitfall: The extra word in word_count_2 check is redundant because Counter objects return 0 for missing keys, and 0 ≠ 1 will correctly exclude these words anyway.

Pitfall 2: Iterating Through Both Dictionaries

The Problem: Some developers might think they need to check words from both directions, leading to duplicate counting or incorrect logic.

Incorrect attempt:

# Wrong: This would count words twice or miss some cases
result = 0
for word in word_count_1:
    if word_count_1[word] == 1 and word_count_2[word] == 1:
        result += 1
for word in word_count_2:
    if word_count_2[word] == 1 and word_count_1[word] == 1:
        result += 1

Why it's wrong: This counts the same qualifying word twice - once when iterating through word_count_1 and again when iterating through word_count_2.

Pitfall 3: Using Regular Dictionary Instead of Counter

The Problem: Using a regular dictionary requires manual handling of missing keys, making the code more error-prone.

Error-prone attempt:

# Using regular dict - more complex and error-prone
word_count_1 = {}
for word in words1:
    word_count_1[word] = word_count_1.get(word, 0) + 1

word_count_2 = {}
for word in words2:
    word_count_2[word] = word_count_2.get(word, 0) + 1

# Need to use .get() to avoid KeyError
result = sum(
    count == 1 and word_count_2.get(word, 0) == 1 
    for word, count in word_count_1.items()
)

Solution: Stick with Counter - it's specifically designed for frequency counting and handles missing keys gracefully by returning 0.

Correct Approach Reminder:

The original solution is already optimal - iterate through one dictionary and check conditions for both. The Counter class handles missing keys automatically, making the code both clean and correct.