2085. Count Common Words With One Occurrence
Problem Description
The problem requires you to find the number of unique strings that appear exactly once in each of the two provided string arrays, namely words1
and words2
. To solve this, you need to determine the strings that are not repeated within their own arrays and then check how many of these non-repeated strings are common to both arrays.
Intuition
To approach this problem effectively, count the occurrences of each string in both arrays independently. This can be achieved by using data structures that map a string to its frequency (like a dictionary in Python). The standard choice for counting objects in Python is the Counter
class from the collections
module, which does exactly that: it creates a frequency map where each key is a string from the array and each value is the count of occurrences of that string.
Once each array has been processed into its own counter (frequency map), the solution lies in comparing these two. You iterate through the items in one of the counter objects, checking for strings that have a count of exactly one. If a string with a count of one in the first counter also has a count of one in the second counter, it means that this string is unique in both arrays. The sum of such unique strings gives you the answer.
Solution Approach
The reference solution approach is straightforward and cleverly utilizes Python's Counter
class from the collections
module to count the frequency of each word in both input arrays words1
and words2
.
Here are the steps followed in the implementation:
- Firstly, two
Counter
objects,cnt1
andcnt2
, are created forwords1
andwords2
respectively. These objects map each word to its frequency in the respective arrays. - Then, we use a list comprehension combined with the
sum
function to iterate through the items ofcnt1
. We only consider the keysk
(words) that have a valuev
(count) of exactly one since we are looking for unique occurrences. - For each of these keys with a count of one in
cnt1
, we check if the corresponding count incnt2
is also exactly one, using the expressioncnt2[k] == 1
. This filters down to words that are unique in both arrays. - If both conditions are satisfied (the word appears exactly once in both
cnt1
andcnt2
), then the condition evaluates toTrue
, which is implicitly interpreted as1
in the summation. - The
sum
function adds up all the1
s, effectively counting the number of strings that meet the specified criteria. - The result of the
sum
is the final answer and is returned by thecountWords
method.
This approach is efficient because it leverages hash maps (via the Counter
object in Python) to count the frequency of elements with O(n) complexity, where n is the size of the input array. Consequently, the overall time complexity of the algorithm is O(n + m), where n is the length of words1
and m is the length of words2
, since each word in both arrays is processed exactly once.
Example Walkthrough
Let's take an example to illustrate how the solution approach works.
Suppose we have two string arrays:
1words1 = ["apple", "banana", "cherry", "date"] 2words2 = ["banana", "cherry", "apple", "elderberry", "fig", "cherry"]
Following the steps outlined in the solution approach:
- Step 1: Use the Counter class to map each word to its frequency in both arrays.
1from collections import Counter 2 3cnt1 = Counter(words1) # Counter({'apple': 1, 'banana': 1, 'cherry': 1, 'date': 1}) 4cnt2 = Counter(words2) # Counter({'banana': 1, 'cherry': 2, 'apple': 1, 'elderberry': 1, 'fig': 1})
We observe that in cnt1
, every word has a frequency of 1, while in cnt2
"cherry" has a frequency of 2 (which means it's not unique) and all others have a frequency of 1.
- Step 2: Using a list comprehension, we iterate through the items of
cnt1
and check if the corresponding count incnt2
is also 1.
1unique_in_both = sum(1 for word in cnt1 if cnt1[word] == 1 and cnt2[word] == 1)
-
Step 3: In our example, "apple" and "banana" are the words that have a count of one in both
cnt1
andcnt2
.- For "apple",
cnt1["apple"]
is 1 andcnt2["apple"]
is also 1. - For "banana",
cnt1["banana"]
is 1 andcnt2["banana"]
is also 1. - "cherry" and "date" do not meet the criteria because "cherry" is not unique in
cnt2
, and "date" does not exist incnt2
at all.
- For "apple",
-
Step 4: So, only "apple" and "banana" are counted, giving us a sum of 2.
Therefore, the countWords
method would return 2
, which is the number of strings that appear exactly once in each of the arrays words1
and words2
.
The example demonstrates the effectiveness of the approach by filtering unique occurrences efficiently through the use of Counter objects and a summation over a conditional check. The final result correctly reflects the number of unique words appearing once in both arrays.
Python Solution
1from collections import Counter
2
3class Solution:
4 def countWords(self, words1: List[str], words2: List[str]) -> int:
5 # Count the occurrences of each word in the first list
6 count_words1 = Counter(words1)
7
8 # Count the occurrences of each word in the second list
9 count_words2 = Counter(words2)
10
11 # Sum the total number of words that appear exactly once in each list
12 return sum(count_words2[word] == 1 for word, count in count_words1.items() if count == 1)
13
Java Solution
1class Solution {
2 public int countWords(String[] words1, String[] words2) {
3 // Count the occurrences of each word in both arrays
4 Map<String, Integer> countWords1 = countOccurrences(words1);
5 Map<String, Integer> countWords2 = countOccurrences(words2);
6
7 int result = 0; // Initialize the result to count the words that appear exactly once in both arrays
8 for (String word : words1) {
9 // For each word in words1, check if it occurs exactly once in both words1 and words2
10 if (countWords1.getOrDefault(word, 0) == 1 && countWords2.getOrDefault(word, 0) == 1) {
11 result++; // Increment the result count for each such word
12 }
13 }
14 return result; // Return the final count of words that appear exactly once in both arrays
15 }
16
17 // Helper method to count occurrences of each word in a given array
18 private Map<String, Integer> countOccurrences(String[] words) {
19 Map<String, Integer> countMap = new HashMap<>(); // Map to store word counts
20 for (String word : words) {
21 // Update the count of each word in the map
22 countMap.put(word, countMap.getOrDefault(word, 0) + 1);
23 }
24 return countMap; // Return the map containing counts of each word
25 }
26}
27
C++ Solution
1#include <vector>
2#include <string>
3#include <unordered_map>
4using namespace std;
5
6class Solution {
7public:
8 int countWords(vector<string>& words1, vector<string>& words2) {
9 // Create two hash maps to store the frequency of each word in words1 and words2.
10 unordered_map<string, int> freqWords1;
11 unordered_map<string, int> freqWords2;
12
13 // Iterate through the first list of words and count their occurrences.
14 for (const auto& word : words1) {
15 freqWords1[word]++;
16 }
17 // Iterate through the second list of words and count their occurrences.
18 for (const auto& word : words2) {
19 freqWords2[word]++;
20 }
21
22 int count = 0; // This will hold the number of words that appear exactly once in both lists.
23 // Iterate through the first list's frequency map.
24 for (const auto& [word, freq] : freqWords1) {
25 // Increment count if the word occurs exactly once in both lists.
26 if (freq == 1 && freqWords2[word] == 1) {
27 count++;
28 }
29 }
30 // Return the final count of words that appear exactly once in each list.
31 return count;
32 }
33};
34
Typescript Solution
1// Import the necessary TypeScript types.
2import { string, number } from 'typescript';
3
4// Define a function to count words that appear exactly once in both lists.
5function countWords(words1: string[], words2: string[]): number {
6 // Create two maps to store the frequency of each word in words1 and words2.
7 const freqWords1: Record<string, number> = {};
8 const freqWords2: Record<string, number> = {};
9
10 // Iterate through the first list of words and count their occurrences.
11 for (const word of words1) {
12 freqWords1[word] = (freqWords1[word] || 0) + 1;
13 }
14
15 // Iterate through the second list of words and count their occurrences.
16 for (const word of words2) {
17 freqWords2[word] = (freqWords2[word] || 0) + 1;
18 }
19
20 let count = 0; // Variable to hold the number of words that appear exactly once in both lists.
21
22 // Iterate through the frequency map of the first list.
23 for (const word in freqWords1) {
24 // Increment count if the word occurs exactly once in both lists.
25 if (freqWords1[word] === 1 && freqWords2[word] === 1) {
26 count++;
27 }
28 }
29
30 // Return the final count of words that appear exactly once in each list.
31 return count;
32}
33
34// Example usage:
35const wordsList1 = ['apple', 'banana', 'cherry'];
36const wordsList2 = ['banana', 'apple', 'durian'];
37const uniqueWordsCount = countWords(wordsList1, wordsList2);
38console.log(`Number of words appearing exactly once in both lists: ${uniqueWordsCount}`);
39
Time and Space Complexity
Time Complexity
The time complexity of the code is determined by several factors:
- Creating the first counter
cnt1
forwords1
: This involves iterating over all elements in thewords1
, so it takesO(n)
time wheren
is the number of elements inwords1
. - Creating the second counter
cnt2
forwords2
: Similarly, this takesO(m)
time wherem
is the number of elements inwords2
. - Iterating over the
cnt1
items and summing: We iterate over the countercnt1
items once, which takesO(u)
time whereu
is the number of unique words inwords1
. The conditional check forcnt2[k] == 1
is anO(1)
operation because of the hash table lookup in the counter.
Therefore, the total time complexity is O(n + m + u)
. In the worst case, where all the words are unique, u
can be equal to n
, simplifying it to O(n + m)
.
Space Complexity
The space complexity is dominated by the two counters cnt1
and cnt2
:
- The counter
cnt1
stores each unique word inwords1
, which takesO(u)
space whereu
is the number of unique words inwords1
. - The counter
cnt2
stores each unique word inwords2
, takingO(v)
space wherev
is the number of unique words inwords2
.
The total space complexity is O(u + v)
. In the worst case, where all the words are unique, u
can be equal to n
and v
equal to m
, which makes the space complexity O(n + m)
.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.