Count Common Words With One Occurrence

Easy
529.

Count Common Words With One Occurrence

Count Common Words With One Occurrence is an easy coding problem on arrays, strings and hash table, asked in Amazon and Infosys interviews.

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 <= 1000
  • 1 <= words1[i].length, words2[j].length <= 30
  • All strings consist of lowercase English letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} words1
 * @param {string[]} words2
 * @return {number}
 */
var countWords = function(words1, words2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 1000
  • 1 <= words1[i].length, words2[j].length <= 30
  • All strings consist of lowercase English letters.

Hints for Count Common Words With One Occurrence

  1. Hint 1

    Count occurrences in each array separately.

  2. Hint 2

    A word qualifies only if its count is exactly 1 in both tallies.

  3. 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

  1. Build a frequency map for words1 and another for words2.
  2. Walk the keys of the first map.
  3. 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.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings