We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Common Words With One Occurrence

Number: 2190

Difficulty: Easy

Paid? No

Companies: Jane Street

Problem Description

Given two arrays of strings, words1 and words2, the task is to count the number of strings that appear exactly once in each of the two arrays.

Key Insights

  • Use hash tables (or dictionaries) to count occurrences in each array.
  • A word is eligible if its frequency is 1 in words1 and also 1 in words2.
  • A second pass over one of the dictionaries can be used to determine the final count.

Space and Time Complexity

Time Complexity: O(n + m) where n and m are the lengths of words1 and words2, respectively. Space Complexity: O(n + m) for storing the frequency counts.

Solution

The solution involves the following steps:

  1. Create two frequency dictionaries, one for words1 and one for words2.
  2. Traverse through words1 to populate its frequency dictionary.
  3. Traverse through words2 to populate its frequency dictionary.
  4. Iterate over one of the frequency dictionaries and for each word, check if it occurs exactly once in both dictionaries.
  5. Count and return the number of such words.

Key data structures used:

  • Hash tables/dictionaries for counting occurrences. Algorithmic approach:
  • Two-pass counting over the arrays and then a single pass to compare counts.

Code Solutions

# Function to count common words with one occurrence in each list
def count_common_words(words1, words2):
    # Dictionary to count frequency in words1
    freq1 = {}
    for word in words1:
        freq1[word] = freq1.get(word, 0) + 1

    # Dictionary to count frequency in words2
    freq2 = {}
    for word in words2:
        freq2[word] = freq2.get(word, 0) + 1

    # Counter for words appearing exactly once in both arrays
    count = 0
    for word in freq1:
        # Check if the word appears exactly once in words1 and exists in words2 with frequency one
        if freq1[word] == 1 and freq2.get(word, 0) == 1:
            count += 1
    return count

# Example usage:
words1 = ["leetcode", "is", "amazing", "as", "is"]
words2 = ["amazing", "leetcode", "is"]
print(count_common_words(words1, words2))  # Output should be 2
← Back to All Questions