2085. Count Common Words With One Occurrence - Solution

Q: Is Count Common Words With One Occurrence easy or hard?

Count Common Words With One Occurrence is classified as an Easy problem. The main concept is frequency counting with hash maps, a fundamental technique for array and string problems. The optimal solution is linear time and straightforward once the counting idea is recognized.

Q: Count Common Words With One Occurrence Python/Java solution

Python typically uses a dictionary or collections.Counter to store word frequencies. Java implementations use HashMap . Both versions iterate through the arrays, build frequency maps, and count words that appear exactly once in both arrays.

The problem

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 <= 1000
1 <= words1[i].length, words2[j].length <= 30
words1[i] and words2[j] consists only of lowercase English letters.

Approach overview

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.

Approach 1: Approach 1: Using Frequency Counters

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.

Python

from collections import Counter

def countCommonWords(words1, words2):
    counter1 = Counter(words1)
    counter2 = Counter(words2)

    common_count = 0
    for word in counter1:
        if counter1[word] == 1 and counter2.get(word, 0) == 1:
            common_count += 1

    return common_count

# Example use
words1 = ["leetcode", "is", "amazing", "as", "is"]
words2 = ["amazing", "leetcode", "is"]

result = countCommonWords(words1, words2)
print("Output:", result)

Java

import java.util.*;

public class CountCommonWords {
    public static int countCommonWords(List<String> words1, List<String> words2) {
        Map<String, Integer> count1 = new HashMap<>();
        Map<String, Integer> count2 = new HashMap<>();

        for (String word : words1) {
            count1.put(word, count1.getOrDefault(word, 0) + 1);
        }

        for (String word : words2) {
            count2.put(word, count2.getOrDefault(word, 0) + 1);
        }

        int commonCount = 0;
        for (String word : count1.keySet()) {
            if (count1.get(word) == 1 && count2.getOrDefault(word, 0) == 1) {
                commonCount++;
            }
        }

        return commonCount;
    }

    public static void main(String[] args) {
        List<String> words1 = Arrays.asList("leetcode", "is", "amazing", "as", "is");
        List<String> words2 = Arrays.asList("amazing", "leetcode", "is");

        int result = countCommonWords(words1, words2);
        System.out.println("Output: " + result);
    }
}

C++

#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>

int countCommonWords(std::vector<std::string>& words1, std::vector<std::string>& words2) {
    std::unordered_map<std::string, int> count1, count2;
    
    for (const std::string& word : words1) {
        count1[word]++;
    }
    
    for (const std::string& word : words2) {
        count2[word]++;
    }
    
    int commonCount = 0;
    for (const auto& pair : count1) {
        if (pair.second == 1 && count2[pair.first] == 1) {
            commonCount++;
        }
    }
    
    return commonCount;
}

int main() {
    std::vector<std::string> words1 = {"leetcode", "is", "amazing", "as", "is"};
    std::vector<std::string> words2 = {"amazing", "leetcode", "is"};
    
    int result = countCommonWords(words1, words2);
    std::cout << "Output: " << result << std::endl;
    
    return 0;
}

JavaScript

function countCommonWords(words1, words2) {
    const count1 = {};
    const count2 = {};

    for (const word of words1) {
        count1[word] = (count1[word] || 0) + 1;
    }

    for (const word of words2) {
        count2[word] = (count2[word] || 0) + 1;
    }

    let commonCount = 0;
    for (const word in count1) {
        if (count1[word] === 1 && count2[word] === 1) {
            commonCount++;
        }
    }

    return commonCount;
}

// Example use
const words1 = ["leetcode", "is", "amazing", "as", "is"];
const words2 = ["amazing", "leetcode", "is"];
console.log("Output:", countCommonWords(words1, words2));

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_WORDS 1000
#define MAX_WORD_LENGTH 31

// Hash Map Entry Structure
typedef struct {
    char word[MAX_WORD_LENGTH];
    int count1;
    int count2;
} Entry;

// Simple Hash Map for Storing Word Counts
typedef struct {
    Entry entries[MAX_WORDS];
    int size;
} HashMap;

// Helper function to find or insert word in hash map
Entry* find_or_insert(HashMap *map, const char *word) {
    for (int i = 0; i < map->size; i++) {
        if (strcmp(map->entries[i].word, word) == 0) {
            return &map->entries[i];
        }
    }
    // Insert new word
    strcpy(map->entries[map->size].word, word);
    map->entries[map->size].count1 = 0;
    map->entries[map->size].count2 = 0;
    return &map->entries[map->size++];
}

// Main function to count common words with exactly one occurrence
int countCommonWords(char words1[][MAX_WORD_LENGTH], int size1, char words2[][MAX_WORD_LENGTH], int size2) {
    HashMap map = { .size = 0 };

    // Count words in words1
    for (int i = 0; i < size1; i++) {
        Entry *entry = find_or_insert(&map, words1[i]);
        entry->count1++;
    }

    // Count words in words2
    for (int i = 0; i < size2; i++) {
        Entry *entry = find_or_insert(&map, words2[i]);
        entry->count2++;
    }

    // Count common words with exactly one occurrence
    int commonCount = 0;
    for (int i = 0; i < map.size; i++) {
        if (map.entries[i].count1 == 1 && map.entries[i].count2 == 1) {
            commonCount++;
        }
    }

    return commonCount;
}

// Example use
int main() {
    char words1[][MAX_WORD_LENGTH] = {"leetcode", "is", "amazing", "as", "is"};
    char words2[][MAX_WORD_LENGTH] = {"amazing", "leetcode", "is"};
    int size1 = 5;
    int size2 = 3;

    int result = countCommonWords(words1, size1, words2, size2);
    printf("Output: %d\n", result);

    return 0;
}

using System;
using System.Collections.Generic;

class CountCommonWords {
    public static int CountCommonWordsOnce(List<string> words1, List<string> words2) {
        Dictionary<string, int> count1 = new Dictionary<string, int>();
        Dictionary<string, int> count2 = new Dictionary<string, int>();

        foreach (string word in words1) {
            if (count1.ContainsKey(word)) {
                count1[word]++;
            } else {
                count1[word] = 1;
            }
        }

        foreach (string word in words2) {
            if (count2.ContainsKey(word)) {
                count2[word]++;
            } else {
                count2[word] = 1;
            }
        }

        int commonCount = 0;
        foreach (var pair in count1) {
            if (pair.Value == 1 && count2.ContainsKey(pair.Key) && count2[pair.Key] == 1) {
                commonCount++;
            }
        }

        return commonCount;
    }

    static void Main() {
        List<string> words1 = new List<string> { "leetcode", "is", "amazing", "as", "is" };
        List<string> words2 = new List<string> { "amazing", "leetcode", "is" };

        int result = CountCommonWordsOnce(words1, words2);
        Console.WriteLine("Output: " + result);
    }
}

This Python solution uses the Counter class from the collections module to easily count word occurrences. It then loops to filter words meeting the condition of appearing once in each list.

Complexity

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.

Try this approach in the editor

Approach 2: Approach 2: Simultaneous Counting with Sets

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.

Python

from collections import Counter

def countCommonWords(words1, words2):
    counter1 = Counter(words1)
    counter2 = Counter(words2)

    uniqueWords1 = {word for word, count in counter1.items() if count == 1}
    uniqueWords2 = {word for word, count in counter2.items() if count == 1}

    return len(uniqueWords1.intersection(uniqueWords2))

# Example use
words1 = ["leetcode", "is", "amazing", "as", "is"]
words2 = ["amazing", "leetcode", "is"]

result = countCommonWords(words1, words2)
print("Output:", result)

Java

import java.util.*;

public class CountCommonWords {
    public static int countCommonWords(List<String> words1, List<String> words2) {
        Map<String, Integer> counter1 = new HashMap<>();
        Map<String, Integer> counter2 = new HashMap<>();
        Set<String> uniqueWords1 = new HashSet<>();
        Set<String> uniqueWords2 = new HashSet<>();

        for (String word : words1) {
            counter1.put(word, counter1.getOrDefault(word, 0) + 1);
        }
        for (String word : words2) {
            counter2.put(word, counter2.getOrDefault(word, 0) + 1);
        }

        for (Map.Entry<String, Integer> entry : counter1.entrySet()) {
            if (entry.getValue() == 1) {
                uniqueWords1.add(entry.getKey());
            }
        }
        for (Map.Entry<String, Integer> entry : counter2.entrySet()) {
            if (entry.getValue() == 1) {
                uniqueWords2.add(entry.getKey());
            }
        }

        uniqueWords1.retainAll(uniqueWords2);
        return uniqueWords1.size();
    }

    public static void main(String[] args) {
        List<String> words1 = Arrays.asList("leetcode", "is", "amazing", "as", "is");
        List<String> words2 = Arrays.asList("amazing", "leetcode", "is");

        int result = countCommonWords(words1, words2);
        System.out.println("Output: " + result);
    }
}

C++

#include <iostream>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <string>

int countCommonWords(const std::vector<std::string>& words1, const std::vector<std::string>& words2) {
    std::unordered_map<std::string, int> counter1, counter2;
    std::unordered_set<std::string> uniqueWords1, uniqueWords2;

    for (const auto& word : words1) {
        counter1[word]++;
    }
    for (const auto& word : words2) {
        counter2[word]++;
    }

    for (const auto& pair : counter1) {
        if (pair.second == 1) {
            uniqueWords1.insert(pair.first);
        }
    }
    for (const auto& pair : counter2) {
        if (pair.second == 1) {
            uniqueWords2.insert(pair.first);
        }
    }

    int commonCount = 0;
    for (const auto& word : uniqueWords1) {
        if (uniqueWords2.count(word)) {
            commonCount++;
        }
    }

    return commonCount;
}

int main() {
    std::vector<std::string> words1 = {"leetcode", "is", "amazing", "as", "is"};
    std::vector<std::string> words2 = {"amazing", "leetcode", "is"};

    int result = countCommonWords(words1, words2);
    std::cout << "Output: " << result << std::endl;

    return 0;
}

JavaScript

function countCommonWords(words1, words2) {
    const counter1 = {};
    const counter2 = {};

    words1.forEach(word => {
        counter1[word] = (counter1[word] || 0) + 1;
    });

    words2.forEach(word => {
        counter2[word] = (counter2[word] || 0) + 1;
    });

    const uniqueWords1 = new Set(Object.keys(counter1).filter(word => counter1[word] === 1));
    const uniqueWords2 = new Set(Object.keys(counter2).filter(word => counter2[word] === 1));

    let commonCount = 0;
    uniqueWords1.forEach(word => {
        if (uniqueWords2.has(word)) {
            commonCount++;
        }
    });

    return commonCount;
}

// Example usage
const words1 = ["leetcode", "is", "amazing", "as", "is"];
const words2 = ["amazing", "leetcode", "is"];
console.log("Output:", countCommonWords(words1, words2));

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdlib.h>

#define MAX_WORDS 1000
#define MAX_WORD_LENGTH 31

typedef struct WordSet {
    char unique[MAX_WORDS][MAX_WORD_LENGTH];
    char duplicate[MAX_WORDS][MAX_WORD_LENGTH];
    int uniqueCount;
    int duplicateCount;
} WordSet;

bool contains(char array[MAX_WORDS][MAX_WORD_LENGTH], int size, const char* word) {
    for (int i = 0; i < size; i++) {
        if (strcmp(array[i], word) == 0) {
            return true;
        }
    }
    return false;
}

void processWords(char words[][MAX_WORD_LENGTH], int size, WordSet* set) {
    for (int i = 0; i < size; i++) {
        const char* word = words[i];
        if (contains(set->unique, set->uniqueCount, word)) {
            set->duplicate[set->duplicateCount++] = word;
        } else if(!contains(set->duplicate, set->duplicateCount, word)) {
            strcpy(set->unique[set->uniqueCount++], word);
        }
    }
}

int countCommonWords(char words1[][MAX_WORD_LENGTH], int size1, char words2[][MAX_WORD_LENGTH], int size2) {
    WordSet set1 = { .uniqueCount = 0, .duplicateCount = 0 };
    WordSet set2 = { .uniqueCount = 0, .duplicateCount = 0 };

    processWords(words1, size1, &set1);
    processWords(words2, size2, &set2);

    int commonCount = 0;
    for (int i = 0; i < set1.uniqueCount; i++) {
        const char* word = set1.unique[i];
        if (!contains(set1.duplicate, set1.duplicateCount, word) &&
            contains(set2.unique, set2.uniqueCount, word) &&
            !contains(set2.duplicate, set2.duplicateCount, word)) {
            commonCount++;
        }
    }

    return commonCount;
}

int main() {
    char words1[][MAX_WORD_LENGTH] = {"leetcode", "is", "amazing", "as", "is"};
    char words2[][MAX_WORD_LENGTH] = {"amazing", "leetcode", "is"};
    int size1 = 5;
    int size2 = 3;

    int result = countCommonWords(words1, size1, words2, size2);
    printf("Output: %d\n", result);

    return 0;
}

using System;
using System.Collections.Generic;

class CountCommonWords {
    public static int CountCommonWordsOnce(List<string> words1, List<string> words2) {
        Dictionary<string, int> counter1 = new Dictionary<string, int>(), counter2 = new Dictionary<string, int>();
        HashSet<string> uniqueWords1 = new HashSet<string>();
        HashSet<string> uniqueWords2 = new HashSet<string>();

        foreach (var word in words1) {
            if (!counter1.ContainsKey(word)) counter1[word] = 0;
            counter1[word]++;
        }
        
        foreach (var word in words2) {
            if (!counter2.ContainsKey(word)) counter2[word] = 0;
            counter2[word]++;
        }

        foreach (var pair in counter1) {
            if (pair.Value == 1) uniqueWords1.Add(pair.Key);
        }

        foreach (var pair in counter2) {
            if (pair.Value == 1) uniqueWords2.Add(pair.Key);
        }

        uniqueWords1.IntersectWith(uniqueWords2);
        return uniqueWords1.Count;
    }

    static void Main() {
        List<string> words1 = new List<string> { "leetcode", "is", "amazing", "as", "is" };
        List<string> words2 = new List<string> { "amazing", "leetcode", "is" };

        int result = CountCommonWordsOnce(words1, words2);
        Console.WriteLine("Output: " + result);
    }
}

In Python, we use set operations to find intersections of unique words confined to being counted once. This approach includes dict and set comprehensions to form and cross-examine sets easily.

Complexity

Time Complexity: O(n + m)
Space Complexity: O(n + m) where n and m are effective counts from both lists.

Try this approach in the editor

Approach 3: Hash Table + Counting

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.

TypeScript

function countWords(words1: string[], words2: string[]): number {
    const cnt1 = new Map<string, number>();
    const cnt2 = new Map<string, number>();
    for (const w of words1) {
        cnt1.set(w, (cnt1.get(w) ?? 0) + 1);
    }
    for (const w of words2) {
        cnt2.set(w, (cnt2.get(w) ?? 0) + 1);
    }
    let ans = 0;
    for (const [w, v] of cnt1) {
        if (v === 1 && cnt2.get(w) === 1) {
            ++ans;
        }
    }
    return ans;
}

func countWords(words1 []string, words2 []string) (ans int) {
	cnt1 := map[string]int{}
	cnt2 := map[string]int{}
	for _, w := range words1 {
		cnt1[w]++
	}
	for _, w := range words2 {
		cnt2[w]++
	}
	for w, v := range cnt1 {
		if v == 1 && cnt2[w] == 1 {
			ans++
		}
	}
	return
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Using Frequency Counters	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.
Approach 2: Simultaneous Counting with Sets	Time Complexity: O(n + m) Space Complexity: O(n + m) where n and m are effective counts from both lists.
Hash Table + Counting	–

Complexity analysis

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.

Frequently asked questions

Is Count Common Words With One Occurrence easy or hard?

Count Common Words With One Occurrence is classified as an Easy problem. The main concept is frequency counting with hash maps, a fundamental technique for array and string problems. The optimal solution is linear time and straightforward once the counting idea is recognized.

Count Common Words With One Occurrence Python/Java solution

Python typically uses a dictionary or collections.Counter to store word frequencies. Java implementations use HashMap<String, Integer>. Both versions iterate through the arrays, build frequency maps, and count words that appear exactly once in both arrays.

How to solve Count Common Words With One Occurrence in O(n)?

Use two hash maps to count word frequencies. First iterate through each array to build frequency tables. Then iterate through the keys of one map and check whether the word has count 1 in both maps. Each operation is constant time on average, giving a linear O(n + m) solution.

What is the best approach for Count Common Words With One Occurrence?

The best approach uses hash map frequency counting. Build two frequency tables for the two arrays and count words that have frequency exactly 1 in both maps. This solution runs in O(n + m) time with O(n + m) extra space and is the approach most interviewers expect.

Is Count Common Words With One Occurrence asked at Google/Amazon/Meta?

Problems involving frequency counting with hash maps are common in interviews at companies like Amazon, Google, and Meta. While this exact question may vary, the underlying pattern of counting elements and comparing frequencies across datasets appears frequently in coding interviews.

What data structure is used in Count Common Words With One Occurrence?

The primary data structure is a hash map (or dictionary) used for frequency counting. Hash sets can also be used in an alternative solution to track words that appear once versus multiple times. Both rely on constant-time average lookup operations.

What is the time complexity of Count Common Words With One Occurrence?

The optimal solution runs in O(n + m) time, where n and m are the lengths of the two arrays. Each word is processed once while building frequency maps, and hash lookups occur in constant time on average. Space complexity is O(n + m) due to storing counts for distinct words.

Count Common Words With One Occurrence solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Using Frequency Counters

Approach 2: Approach 2: Simultaneous Counting with Sets

Approach 3: Hash Table + Counting

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Count Common Words With One Occurrence solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Using Frequency Counters

Approach 2: Approach 2: Simultaneous Counting with Sets

Approach 3: Hash Table + Counting

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems