algoadvance

Leetcode 2085. Count Common Words With One Occurrence

Problem Statement

You are given two string arrays words1 and words2. A word is common if it appears exactly once in each of the arrays.

Return the number of common words with one occurrence.

Example 1:

Input: words1 = ["leetcode","is","amazing","as","is"], words2 = ["amazing","leetcode","is"]
Output: 2
Explanation:
- "leetcode" appears exactly once in each of the arrays.
- "amazing" appears exactly once in each of the arrays.
- "is" appears in each of the arrays, but there are 2 "is" in words1.
- "as" appears only in words1.
Hence, there are 2 common words with one occurrence each.

Example 2:

Input: words1 = ["b","bb","bbb"], words2 = ["a","aa","aaa"]
Output: 0
Explanation: There are no common words that appear exactly once in each of the arrays.

Example 3:

Input: words1 = ["a","ab"], words2 = ["a","a","a","ab"]
Output: 1
Explanation: The only word that appears exactly once in each of the arrays is "ab".

Constraints:

Clarifying Questions

  1. Can the input arrays be empty?
    • No, as per the constraints, the minimum length of each array is 1.
  2. Do we need to consider the word case (uppercase vs lowercase)?
    • No, all the words consist only of lowercase English letters.
  3. Should we consider words that appear more than once in either array?
    • No, we are only interested in words that appear exactly once in each array.

Code

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int countWords(String[] words1, String[] words2) {
        Map<String, Integer> count1 = new HashMap<>();
        Map<String, Integer> count2 = new HashMap<>();
        
        // Count frequencies in words1
        for (String word : words1) {
            count1.put(word, count1.getOrDefault(word, 0) + 1);
        }
        
        // Count frequencies in words2
        for (String word : words2) {
            count2.put(word, count2.getOrDefault(word, 0) + 1);
        }
        
        int commonCount = 0;
        
        // Find common words with exactly one occurrence in both arrays
        for (String word : count1.keySet()) {
            if (count1.get(word) == 1 && count2.getOrDefault(word, 0) == 1) {
                commonCount++;
            }
        }
        
        return commonCount;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        
        // Test cases
        String[] words1_1 = {"leetcode","is","amazing","as","is"};
        String[] words2_1 = {"amazing","leetcode","is"};
        System.out.println(sol.countWords(words1_1, words2_1)); // Output: 2

        String[] words1_2 = {"b","bb","bbb"};
        String[] words2_2 = {"a","aa","aaa"};
        System.out.println(sol.countWords(words1_2, words2_2)); // Output: 0

        String[] words1_3 = {"a","ab"};
        String[] words2_3 = {"a","a","a","ab"};
        System.out.println(sol.countWords(words1_3, words2_3)); // Output: 1
    }
}

Strategy

  1. Count occurrences: Use two hash maps to count the frequency of each word in words1 and words2.
  2. Check for common words: Iterate through one of the maps and check if a word has exactly one occurrence in both maps.
  3. Count the common words.

Time Complexity

The time complexity of this solution is O(n + m), where n is the length of words1 and m is the length of words2. This is because:

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI