Count Common Words With One Occurrence - Leetcode Solution

Problem Statement:

Given two strings A and B, return the count of common words with one occurrence in both strings.

A word is defined as a sequence of non-space characters. Each word in A and B is case-insensitive.

Example 1:

Input: A = "this apple is sweet", B = "this apple is sour" Output: 1 Explanation: Both A and B have one "sweet".

Example 2:

Input: A = "apple apple", B = "banana" Output: 0

Solution:

To solve the problem, we can follow the below steps:

1. Convert the given strings A and B to lowercase using the lower() method as all words in A and B are case-insensitive.

2. Split the string A into a list of words using the split() method and store them in a list.

3. Repeat Step 2 for string B and store the words in a separate list.

4. Create a dictionary to store the frequency count of words in both lists.

5. Iterate through each word in list A and update the frequency count in the dictionary.

6. Iterate through each word in list B and check if the word is already present in the dictionary with a frequency of 1.

7. If the word is present with a frequency of 1, increase the count variable by 1.

8. Return the count variable as the final answer.

Python code:

def countCommonWords(A: str, B: str) -> int:
    # Convert the strings to lowercase
    A = A.lower()
    B = B.lower()
    
    # Split the strings into list of words
    A_words = A.split()
    B_words = B.split()
    
    # Create a dictionary to store the frequency of words
    word_count = {}
    
    # Iterate through each word in A and update the count
    for word in A_words:
        if word not in word_count:
            word_count[word] = 1
        else:
            word_count[word] += 1
    
    # Iterate through each word in B and check if it is already present in the dictionary with a count of 1
    count = 0
    for word in B_words:
        if word in word_count and word_count[word] == 1:
            count += 1
    
    return count

Time Complexity Analysis:

1. Converting the strings to lowercase takes O(n) time, where n is the length of the strings.

2. Splitting the strings into lists takes O(n) time.

3. Updating the dictionary with frequency count takes O(n) time.

4. Iterating through each word in B and checking its frequency in the dictionary takes O(n) time.

Therefore, the overall time complexity of the algorithm is O(n).

Space Complexity Analysis:

The space complexity of the algorithm is O(n) as we are using extra space to store the words in lists and the frequency count in a dictionary.

1