LeetCode Problem 2085

Difficulty: 🟢 Easy
Topics: Array, Hash Table, String, Counting

Solution

LeetCode 2085, Count Common Words With One Occurrence

Problem Understanding

This problem gives us two arrays of strings, words1 and words2. Our task is to count how many strings appear exactly once in both arrays.

The key detail is that a word only qualifies if:

1. It appears exactly one time in words1
2. It appears exactly one time in words2

If either array contains the word multiple times, then that word does not count.

For example, consider:

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

The word "leetcode" appears once in both arrays, so it counts.

The word "amazing" also appears once in both arrays, so it counts.

The word "is" appears twice in words1, so even though it appears in words2, it does not count.

The input arrays can each contain up to 1000 words, and each word can have up to 30 lowercase English letters. These constraints are small enough that many approaches would work in practice, but the problem is fundamentally about counting frequencies efficiently.

The important observation is that the problem is not asking whether words merely exist in both arrays. It specifically requires frequency counts. That means we must track how many times each word appears in each array.

Several edge cases are important:

• A word may exist in one array but not the other.
• A word may appear multiple times in one array and once in the other.
• All words may be distinct.
• All words may be repeated many times.
• The arrays may contain only one element each.

A naive implementation that repeatedly scans arrays for counts could become unnecessarily slow, especially if repeated for every word.

Approaches

Brute Force Approach

The brute force solution checks every unique word and manually counts how many times it appears in both arrays.

One way to do this is:

1. Iterate through every word in words1
2. Count its occurrences in words1
3. Count its occurrences in words2
4. If both counts equal 1, increment the answer

The counting operation itself requires scanning the arrays repeatedly. Since each lookup may take linear time, the total complexity becomes quadratic.

This approach is correct because it explicitly verifies the exact frequency conditions required by the problem. However, it is inefficient because the same counting work is repeated many times.

Optimal Approach

The better solution uses hash maps, also called dictionaries in Python or maps in Go, to store word frequencies.

The key insight is that frequency counting is exactly what hash maps are designed for. Instead of repeatedly scanning arrays, we can preprocess each array once and store how many times each word appears.

After building the two frequency maps:

• Check every word in the first map
• If its frequency is 1 in both maps, count it

This reduces repeated work and gives an efficient linear-time solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × m + n²)	O(1)	Repeatedly scans arrays to count occurrences
Optimal	O(n + m)	O(n + m)	Uses hash maps for frequency counting

Here, n is the length of words1 and m is the length of words2.

Algorithm Walkthrough

1. Create a hash map for words1.

This map stores each word as a key and its number of occurrences as the value. For example:

{"leetcode": 1, "is": 2, "amazing": 1, "as": 1}

Using a hash map allows constant average-time frequency updates. 2. Create another hash map for words2.

This performs the same frequency counting for the second array. 3. Initialize a variable called common_count to 0.

This variable stores the number of valid words that appear exactly once in both arrays. 4. Iterate through the keys in the first frequency map.

For each word:

• Check whether its count in words1 equals 1
• Check whether its count in words2 also equals 1

If both conditions are true, increment common_count. 5. Return common_count.

After all words are processed, the variable contains the final answer.

Why it works

The algorithm works because the frequency maps store the exact number of occurrences for every word in both arrays. A word satisfies the problem condition if and only if its stored frequency equals 1 in both maps. Since every word frequency is computed correctly during preprocessing, the final count is guaranteed to be correct.

Python Solution

from typing import List
from collections import Counter

class Solution:
    def countWords(self, words1: List[str], words2: List[str]) -> int:
        frequency1 = Counter(words1)
        frequency2 = Counter(words2)

        common_count = 0

        for word in frequency1:
            if frequency1[word] == 1 and frequency2[word] == 1:
                common_count += 1

        return common_count

The implementation begins by importing Counter from Python's collections module. Counter automatically builds a frequency map from a list of words.

frequency1 stores the counts for words1, while frequency2 stores the counts for words2.

The variable common_count keeps track of how many valid words have been found.

The loop iterates through every unique word in frequency1. For each word, the code checks whether the count equals 1 in both maps. If so, the answer is incremented.

Finally, the method returns the total count.

This implementation directly follows the algorithm described earlier and uses Python's built-in data structures to keep the code concise and efficient.

Go Solution

func countWords(words1 []string, words2 []string) int {
	frequency1 := make(map[string]int)
	frequency2 := make(map[string]int)

	for _, word := range words1 {
		frequency1[word]++
	}

	for _, word := range words2 {
		frequency2[word]++
	}

	commonCount := 0

	for word, count := range frequency1 {
		if count == 1 && frequency2[word] == 1 {
			commonCount++
		}
	}

	return commonCount
}

The Go implementation uses map[string]int to store word frequencies.

Unlike Python's Counter, Go does not provide automatic frequency counting utilities in the standard library, so the counts are built manually using loops.

Looking up a nonexistent key in a Go map automatically returns the zero value for the type, which is 0 for integers. This makes the condition:

frequency2[word] == 1

safe even when the word does not exist in frequency2.

No special handling is required for empty slices because the loops naturally handle them correctly.

Worked Examples

Example 1

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

Step 1, Build frequency map for words1

Word	Frequency
leetcode	1
is	2
amazing	1
as	1

Step 2, Build frequency map for words2

Word	Frequency
amazing	1
leetcode	1
is	1

Step 3, Check words

Word	Count in words1	Count in words2	Valid?
leetcode	1	1	Yes
is	2	1	No
amazing	1	1	Yes
as	1	0	No

Final answer:

2

Example 2

words1 = ["b","bb","bbb"]
words2 = ["a","aa","aaa"]

Frequency maps

words1

Word	Frequency
b	1
bb	1
bbb	1

words2

Word	Frequency
a	1
aa	1
aaa	1

No words exist in both arrays.

Final answer:

0

Example 3

words1 = ["a","ab"]
words2 = ["a","a","a","ab"]

Frequency maps

words1

Word	Frequency
a	1
ab	1

words2

Word	Frequency
a	3
ab	1

Validation

Word	Count in words1	Count in words2	Valid?
a	1	3	No
ab	1	1	Yes

Final answer:

1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m)	Each array is traversed once to build frequency maps
Space	O(n + m)	Hash maps store frequencies for unique words

The algorithm performs a single pass through each array to build the frequency maps. Hash map insertions and lookups take constant average time, so the total running time is linear in the size of the input.

The space complexity is also linear because, in the worst case, every word is unique and must be stored in the maps.

Test Cases

from typing import List

class Solution:
    def countWords(self, words1: List[str], words2: List[str]) -> int:
        from collections import Counter

        frequency1 = Counter(words1)
        frequency2 = Counter(words2)

        common_count = 0

        for word in frequency1:
            if frequency1[word] == 1 and frequency2[word] == 1:
                common_count += 1

        return common_count

solution = Solution()

assert solution.countWords(
    ["leetcode", "is", "amazing", "as", "is"],
    ["amazing", "leetcode", "is"]
) == 2  # provided example 1

assert solution.countWords(
    ["b", "bb", "bbb"],
    ["a", "aa", "aaa"]
) == 0  # provided example 2

assert solution.countWords(
    ["a", "ab"],
    ["a", "a", "a", "ab"]
) == 1  # provided example 3

assert solution.countWords(
    ["a"],
    ["a"]
) == 1  # smallest valid matching case

assert solution.countWords(
    ["a"],
    ["b"]
) == 0  # single elements do not match

assert solution.countWords(
    ["x", "x"],
    ["x"]
) == 0  # repeated in first array

assert solution.countWords(
    ["x"],
    ["x", "x"]
) == 0  # repeated in second array

assert solution.countWords(
    ["x", "x"],
    ["x", "x"]
) == 0  # repeated in both arrays

assert solution.countWords(
    ["a", "b", "c"],
    ["a", "b", "c"]
) == 3  # all words unique and shared

assert solution.countWords(
    ["apple", "banana", "apple", "orange"],
    ["banana", "orange", "orange"]
) == 1  # only banana appears once in both

assert solution.countWords(
    ["same", "same", "same"],
    ["same", "same"]
) == 0  # no word appears exactly once

assert solution.countWords(
    ["unique"],
    ["unique", "extra"]
) == 1  # one valid shared word

Test	Why
Example 1	Validates normal mixed frequencies
Example 2	Validates no shared words
Example 3	Validates repeated frequency rejection
["a"], ["a"]	Smallest positive case
["a"], ["b"]	Smallest negative case
Repeated in first array	Ensures duplicates invalidate result
Repeated in second array	Ensures duplicates invalidate result
Repeated in both arrays	Ensures duplicates never count
All unique and shared	Validates multiple successful matches
Mixed duplicate scenario	Tests selective counting
All repeated	Ensures answer can be zero
One shared unique word	Tests partial overlap

Edge Cases

One important edge case occurs when a word appears multiple times in one array but exactly once in the other. A buggy implementation might incorrectly count such a word simply because it exists in both arrays. For example:

words1 = ["a", "a"]
words2 = ["a"]

The correct answer is 0, because "a" does not appear exactly once in words1. The frequency-map approach handles this correctly by explicitly checking both counts.

Another important edge case is when the arrays contain no overlapping words at all. For example:

words1 = ["x", "y"]
words2 = ["a", "b"]

A naive implementation that assumes matching keys exist could fail or produce incorrect results. In both Python and Go, missing keys safely evaluate to 0, so the implementation correctly returns 0.

A third edge case occurs when every word is unique and shared across both arrays. For example:

words1 = ["a", "b", "c"]
words2 = ["a", "b", "c"]

In this scenario, every word should count. The implementation correctly identifies all three words because each has frequency 1 in both maps.

A final edge case involves arrays of minimum size. The constraints allow arrays with only one element. For example:

words1 = ["hello"]
words2 = ["hello"]

The implementation handles this naturally because the frequency maps contain exactly one entry each, and the comparison logic remains unchanged.