Count Common Words With One Occurrence

easy array hash map string counting

Problem

Given two string arrays words1 and words2, return the number of strings that appear exactly once in each of the two arrays.

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

Output2

"leetcode" and "amazing" each occur exactly once in both arrays.

words1

words2

def count_words(words1, words2):
    from collections import Counter
    c1, c2 = Counter(words1), Counter(words2)
    return sum(1 for w in c1 if c1[w] == 1 and c2.get(w, 0) == 1)

function countWords(words1, words2) {
  const c1 = new Map(), c2 = new Map();
  for (const w of words1) c1.set(w, (c1.get(w) || 0) + 1);
  for (const w of words2) c2.set(w, (c2.get(w) || 0) + 1);
  let ans = 0;
  for (const [w, v] of c1) if (v === 1 && c2.get(w) === 1) ans++;
  return ans;
}

class Solution {
    public int countWords(String[] words1, String[] words2) {
        Map<String, Integer> c1 = new HashMap<>(), c2 = new HashMap<>();
        for (String w : words1) c1.merge(w, 1, Integer::sum);
        for (String w : words2) c2.merge(w, 1, Integer::sum);
        int ans = 0;
        for (Map.Entry<String, Integer> e : c1.entrySet())
            if (e.getValue() == 1 && c2.getOrDefault(e.getKey(), 0) == 1) ans++;
        return ans;
    }
}

int countWords(vector<string>& w1, vector<string>& w2) {
    unordered_map<string, int> c1, c2;
    for (auto& w : w1) c1[w]++;
    for (auto& w : w2) c2[w]++;
    int ans = 0;
    for (auto& [w, v] : c1)
        if (v == 1 && c2[w] == 1) ans++;
    return ans;
}

Explanation

We want words that appear exactly once in each of the two arrays. The clean way is to count how many times every word shows up in each array, then compare those counts.

We build two frequency maps, c1 for words1 and c2 for words2, using Counter. Each maps a word to how many times it occurs.

Then we walk through the words in c1 and keep a word only when both conditions hold: c1[w] == 1 and c2.get(w, 0) == 1. The get(w, 0) safely returns 0 for words missing from the second array. We add up how many words pass.

Example: words1 = ["leetcode","is","amazing","as","is"], words2 = ["amazing","leetcode","is"]. Here "is" appears twice in words1 so it fails. "leetcode" and "amazing" each appear once in both, so the answer is 2.

Counting is linear in the size of both arrays, and the final comparison is one quick scan of the map, so the whole thing is fast.

Time: O(n + m) Space: O(n + m)