884. Uncommon Words from Two Sentences - Explanation

Problem Link

1. Hash Map - I

Intuition

A word is uncommon if it appears exactly once across both sentences. We can combine both sentences and count the frequency of each word. Any word with a count of 1 is uncommon.

Algorithm

1. Split both sentences into words and combine them.
2. Use a hash map to count the frequency of each word.
3. Iterate through the hash map and collect all words with a count of 1.
4. Return the list of uncommon words.

class Solution:
    def uncommonFromSentences(self, s1: str, s2: str) -> List[str]:
        count = defaultdict(int)
        for w in s1.split(" ") + s2.split(" "):
            count[w] += 1

        res = []
        for w, cnt in count.items():
            if cnt == 1:
                res.append(w)
        return res

Time & Space Complexity

• Time complexity: $O(n + m)$
• Space complexity: $O(n + m)$

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

---

2. Hash Map - II

Intuition

This is a more concise version of the same approach. We use built-in functions like Counter (in Python) or stream operations (in Java) to reduce boilerplate while maintaining the same logic.

Algorithm

1. Combine and split both sentences into words.
2. Count word frequencies using a built-in counter or grouping function.
3. Filter to keep only words with count equal to 1.
4. Return the filtered words.

class Solution:
    def uncommonFromSentences(self, s1: str, s2: str) -> List[str]:
        return [w for w, cnt in Counter(s1.split(" ") + s2.split(" ")).items() if cnt == 1]

Time & Space Complexity

• Time complexity: $O(n + m)$
• Space complexity: $O(n + m)$

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