Problem Description

You are given two sentences s1 and s2, where each sentence is a string containing words separated by single spaces. Each word in the sentences consists only of lowercase letters.

A word is considered uncommon if it meets the following criteria:

• It appears exactly once in one of the sentences
• It does not appear at all in the other sentence

Your task is to find all uncommon words from both sentences and return them as a list. The words can be returned in any order.

For example, if s1 = "this apple is sweet" and s2 = "this apple is sour", the uncommon words would be ["sweet", "sour"] because:

• "sweet" appears once in s1 but not in s2
• "sour" appears once in s2 but not in s1
• "this", "apple", and "is" appear in both sentences, so they are not uncommon

The solution uses a hash table (Counter) to count the occurrences of all words from both sentences combined. Since an uncommon word must appear exactly once total (once in one sentence and zero times in the other), we simply return all words that have a count of 1 in the combined frequency map.

Intuition

The key insight is to recognize what makes a word "uncommon" - it must appear exactly once in one sentence and not at all in the other.

If we think about this carefully, when we combine both sentences together, an uncommon word will have a total count of exactly 1. Why? Because:

• If a word appears once in s1 and zero times in s2, its total count is 1 + 0 = 1
• If a word appears zero times in s1 and once in s2, its total count is 0 + 1 = 1

Any other scenario would not qualify as uncommon:

• If a word appears in both sentences (even once each), its total count would be at least 2
• If a word appears multiple times in one sentence, its total count would be greater than 1

This observation leads us to a simple approach: instead of tracking which sentence each word comes from, we can just count all words from both sentences together. Any word with a count of exactly 1 is uncommon by definition.

This transforms the problem from "find words that appear once in one sentence but not in the other" to simply "find words that appear exactly once in total", which is much easier to implement using a frequency counter.

Solution Approach

The implementation uses a hash table to count word frequencies across both sentences:

1. Split and Count Words: First, we split both sentences into individual words using the split() method, which separates words by spaces. The Counter class from Python's collections module automatically creates a frequency map for each sentence.

2. Combine Frequency Maps: We add the two Counter objects together using the + operator. This combines the counts from both sentences. For example:

   • If "apple" appears once in s1 and once in s2, the combined count is 2
   • If "sweet" appears once in s1 and not in s2, the combined count is 1
   • If "sour" appears not in s1 but once in s2, the combined count is 1

3. Filter Words with Count 1: We iterate through the combined counter using cnt.items(), which gives us (word, count) pairs. Using a list comprehension, we filter and collect only those words where the count v equals 1.

The complete solution in one line:

cnt = Counter(s1.split()) + Counter(s2.split())
return [s for s, v in cnt.items() if v == 1]

Time Complexity: O(n + m) where n and m are the lengths of the two sentences, as we need to process each word once.

Space Complexity: O(n + m) for storing the words in the hash table.

Example Walkthrough

Let's walk through the solution with a concrete example:

Input:

• s1 = "apple orange banana"
• s2 = "apple grape banana banana"

Step 1: Split and count words in each sentence

First, we split s1 into words and count them:

• s1.split() → ["apple", "orange", "banana"]
• Counter(s1.split()) → {"apple": 1, "orange": 1, "banana": 1}

Then split s2 into words and count them:

• s2.split() → ["apple", "grape", "banana", "banana"]
• Counter(s2.split()) → {"apple": 1, "grape": 1, "banana": 2}

Step 2: Combine the frequency maps

Add the two counters together:

{"apple": 1, "orange": 1, "banana": 1} + {"apple": 1, "grape": 1, "banana": 2}
= {"apple": 2, "orange": 1, "banana": 3, "grape": 1}

The combined counter shows:

• "apple": appears 2 times total (once in each sentence)
• "orange": appears 1 time total (only in s1)
• "banana": appears 3 times total (once in s1, twice in s2)
• "grape": appears 1 time total (only in s2)

Step 3: Filter words with count = 1

Iterate through the combined counter and select words with count exactly 1:

• "apple": count is 2 → skip
• "orange": count is 1 → include ✓
• "banana": count is 3 → skip
• "grape": count is 1 → include ✓

Result: ["orange", "grape"]

These are the uncommon words because:

• "orange" appears exactly once in s1 and not at all in s2
• "grape" appears exactly once in s2 and not at all in s1

Solution Implementation

Time and Space Complexity

Time Complexity: O(m + n)

The time complexity breaks down as follows:

• s1.split() takes O(m) time to split string s1 into words
• s2.split() takes O(n) time to split string s2 into words
• Creating Counter for s1 words takes O(m) time (iterating through all characters/words)
• Creating Counter for s2 words takes O(n) time (iterating through all characters/words)
• Adding two Counter objects takes O(m + n) time in the worst case (combining all unique keys)
• The list comprehension iterates through all items in the combined counter, which is at most O(m + n) unique words
• Overall: O(m) + O(n) + O(m + n) = O(m + n)

Space Complexity: O(m + n)

The space complexity breaks down as follows:

• s1.split() creates a list that takes O(m) space (storing all characters from s1 as words)
• s2.split() creates a list that takes O(n) space (storing all characters from s2 as words)
• The Counter objects store at most all unique words from both strings, requiring O(m + n) space
• The result list stores words that appear exactly once, which is at most O(m + n) words
• Overall: O(m + n)

Where m and n are the lengths of strings s1 and s2, respectively.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Problem Definition

A common mistake is thinking that uncommon words are those that appear in one sentence but not the other, regardless of frequency. This leads to incorrect solutions like:

# INCORRECT approach
def uncommonFromSentences(self, s1: str, s2: str) -> List[str]:
    words1 = set(s1.split())
    words2 = set(s2.split())
    return list((words1 - words2) | (words2 - words1))

This fails when a word appears multiple times in one sentence. For example, with s1 = "apple apple" and s2 = "banana", this would incorrectly return ["apple", "banana"] when the answer should be just ["banana"] (since "apple" appears twice).

Solution: Remember that uncommon words must appear exactly once in one sentence and not at all in the other. The combined count approach correctly handles this by ensuring only words with total count 1 are selected.

2. Incorrect String Splitting

Using incorrect splitting methods or forgetting to handle edge cases:

# INCORRECT - using wrong split delimiter
words = s1.split(',')  # Wrong delimiter

# INCORRECT - manual splitting that doesn't handle multiple spaces
words = s1.split(' ')  # Fails with multiple consecutive spaces

Solution: Use split() without arguments, which correctly handles any amount of whitespace:

words = s1.split()  # Correctly splits on any whitespace

3. Not Handling Empty Strings or Edge Cases

Failing to consider empty or single-word sentences:

# Potential issue if not careful
s1 = ""
s2 = "hello world"
# Need to ensure empty strings are handled properly

Solution: The split() method on an empty string returns an empty list, and Counter() handles empty lists correctly, so the provided solution naturally handles these edge cases.

4. Inefficient Duplicate Checking

Attempting to manually check for duplicates instead of using the Counter approach:

# INEFFICIENT approach
def uncommonFromSentences(self, s1: str, s2: str) -> List[str]:
    result = []
    words1 = s1.split()
    words2 = s2.split()
  
    for word in words1:
        if words1.count(word) == 1 and word not in words2:
            result.append(word)
  
    for word in words2:
        if words2.count(word) == 1 and word not in words1:
            result.append(word)
  
    return result

This has O(n²) time complexity due to the count() method being called for each word.

Solution: Use the Counter approach which processes all words in O(n + m) time with a single pass through each sentence.