Count Common Words With One Occurrence — Problem & Solution
Count Common Words With One Occurrence solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Count Common Words With One Occurrence is an easy coding problem on arrays, strings and hash table, asked in Amazon and Infosys interviews.
- Difficulty: Easy
- Topics: Arrays, Strings, Hash Table
- Asked at: Amazon, Infosys
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
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" and "amazing" each appear once in both; "is" appears twice in words1.
Example 2
Input: words1 = ["b","bb","bbb"], words2 = ["a","aa","aaa"]
Output: 0
Example 3
Input: words1 = ["a","ab"], words2 = ["a","a","a","ab"]
Output: 1
Constraints
1 <= words1.length, words2.length <= 10001 <= words1[i].length, words2[j].length <= 30All strings consist of lowercase English letters.
Hints for Count Common Words With One Occurrence
Hint 1
Count occurrences in each array separately.
Hint 2
A word qualifies only if its count is exactly 1 in both tallies.
Hint 3
Iterate over one tally and look the word up in the other.
How to solve Count Common Words With One Occurrence
Two frequency maps reduce the question to a per-word test: count 1 on the left and count 1 on the right.
Approach
- Build a frequency map for
words1and another forwords2. - Walk the keys of the first map.
- Count a key when its value is 1 and the second map maps it to 1 as well.
Why it works
Both conditions are independent per word, so the count is a simple sum over the distinct words of one array — and any qualifying word necessarily appears in that array.
Complexity
- Time —
O(total characters) - Space —
O(n + m)
Pitfalls
- Using sets loses the multiplicity, so words appearing twice would wrongly qualify.
- Counting over the union of both key sets double-counts if you are not careful; iterating one map is enough.
Reference solution
Python
from typing import List
def countWords(words1: List[str], words2: List[str]) -> int:
a = {}
b = {}
for w in words1:
a[w] = a.get(w, 0) + 1
for w in words2:
b[w] = b.get(w, 0) + 1
return sum(1 for w, c in a.items() if c == 1 and b.get(w, 0) == 1)Java
public static int countWords(String[] words1, String[] words2) {
HashMap<String, Integer> a = new HashMap<>();
HashMap<String, Integer> b = new HashMap<>();
for (String w : words1) a.put(w, a.getOrDefault(w, 0) + 1);
for (String w : words2) b.put(w, b.getOrDefault(w, 0) + 1);
int count = 0;
for (Map.Entry<String, Integer> e : a.entrySet()) {
if (e.getValue() == 1 && b.getOrDefault(e.getKey(), 0) == 1) count++;
}
return count;
}C++
int countWords(vector<string>& words1, vector<string>& words2) {
unordered_map<string, int> a, b;
for (auto& w : words1) a[w]++;
for (auto& w : words2) b[w]++;
int count = 0;
for (auto& e : a) {
if (e.second == 1 && b.count(e.first) && b[e.first] == 1) count++;
}
return count;
}JavaScript
var countWords = function(words1, words2) {
function tally(arr) {
const m = {};
for (let i = 0; i < arr.length; i++) m[arr[i]] = (m[arr[i]] || 0) + 1;
return m;
}
const a = tally(words1);
const b = tally(words2);
let count = 0;
const keys = Object.keys(a);
for (let i = 0; i < keys.length; i++) {
if (a[keys[i]] === 1 && b[keys[i]] === 1) count++;
}
return count;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.