algoadvance

Leetcode 2085. Count Common Words With One Occurrence

Problem Statement

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

Clarifying Questions

1. Input Constraints:
   • What is the maximum length of words1 and words2?
   • Are the strings within the arrays guaranteed to be non-empty?
2. Output Constraints:
   • What should be returned if no word fits the criteria? (Assumption: return 0)

Code

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

using namespace std;

int countWords(vector<string>& words1, vector<string>& words2) {
    unordered_map<string, int> count1, count2;
    
    // Count occurrences in words1
    for (const auto& word : words1) {
        count1[word]++;
    }
    
    // Count occurrences in words2
    for (const auto& word : words2) {
        count2[word]++;
    }
    
    int result = 0;
    // Iterate over the first map and check the conditions in the second map
    for (const auto& entry : count1) {
        if (entry.second == 1 && count2[entry.first] == 1) {
            result++;
        }
    }
    
    return result;
}

int main() {
    vector<string> words1 = {"leetcode", "is", "amazing", "as", "is"};
    vector<string> words2 = {"amazing", "leetcode", "is"};
    
    cout << "Number of common words with one occurrence: " << countWords(words1, words2) << endl;
    return 0;
}

Strategy

1. Use two hash maps to store the counts of each word in words1 and words2.
2. Traverse through the first map to check if each word has exactly one occurrence in both arrays.
3. Count the words that meet the criteria and return this count.

Time Complexity

• O(N + M):
  • N is the length of words1.
  • M is the length of words2.
  • Constructing the hash maps takes linear time relative to the lengths of the arrays.
  • Iterating through the hash maps to count common words also takes linear time.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?