Difficulty: 🟢 Easy
Topics: Hash Table, String, Counting

Solution

LeetCode 884, Uncommon Words from Two Sentences

Problem Understanding

This problem asks us to find all words that are considered "uncommon" between two sentences.

Each sentence is made up of lowercase words separated by single spaces. A word is considered uncommon if it satisfies two conditions:

It appears exactly once in one sentence.
It does not appear at all in the other sentence.

We are given two input strings, s1 and s2. Each string represents a sentence. The task is to return a list containing every word that is uncommon across the two sentences.

For example, consider:

s1 = "this apple is sweet"
s2 = "this apple is sour"

The words "this" and "apple" appear in both sentences, so they are not uncommon. The word "is" also appears in both sentences. The word "sweet" appears exactly once in s1 and nowhere in s2, so it is uncommon. Similarly, "sour" appears exactly once in s2 and nowhere in s1, so it is also uncommon.

The constraints are very small:

Each sentence length is at most 200 characters.
Words contain only lowercase English letters.
Words are separated by exactly one space.

These constraints tell us that efficiency is not a major concern, since the total number of words is small. However, the problem is fundamentally about counting frequencies, so using a hash map is the most natural and clean solution.

There are several important edge cases to consider:

A word may appear multiple times in the same sentence, which immediately disqualifies it from being uncommon.
A word may appear once in each sentence, which also disqualifies it.
One sentence may contain only repeated words while the other contains a single valid uncommon word.
The answer can be returned in any order, so ordering is not important.

The problem guarantees valid formatting, meaning:

No leading or trailing spaces
Exactly one space between words
Only lowercase letters and spaces

Because of these guarantees, splitting the sentence by spaces is safe and straightforward.

Approaches

Brute Force Approach

A brute force solution would examine every unique word and manually count how many times it appears in both sentences.

One way to do this is:

Split both sentences into word arrays.
Combine all distinct words into a set.
For each word, scan both arrays and count occurrences.
If the total occurrence count is exactly one, add it to the answer.

This works because the definition of an uncommon word depends entirely on frequency counts. If a word appears once globally across both sentences, then it must appear exactly once in one sentence and zero times in the other.

However, this approach repeatedly scans the word arrays for each candidate word. If there are n total words and u unique words, the repeated counting leads to unnecessary work.

Even though the constraints are small enough for this approach to pass, it is inefficient compared to a frequency map solution.

Optimal Approach

The key insight is that this problem is fundamentally a frequency counting problem.

Instead of repeatedly counting occurrences, we can count every word exactly once using a hash map. After building the frequency map, any word with frequency 1 is uncommon.

This works because:

If a word appears once total across both sentences, then it appears in exactly one sentence and nowhere else.
If a word appears more than once, either within the same sentence or across both sentences, it is not uncommon.

A hash map allows constant time frequency updates and lookups, making the solution both simple and efficient.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Repeatedly scans word lists to count frequencies
Optimal	O(n)	O(n)	Uses a hash map to count frequencies in one pass

Here, n represents the total number of words across both sentences.

Algorithm Walkthrough

Optimal Algorithm

Split both sentences into lists of words.

We use the built in string splitting operation because the input format guarantees single spaces between words. 2. Create a hash map to store word frequencies.

The keys are words, and the values are the number of times each word appears across both sentences. 3. Traverse all words from the first sentence.

For each word, increment its frequency count in the hash map. 4. Traverse all words from the second sentence.

Again, increment the frequency count for each word. 5. Create an empty result list.

This list will store all uncommon words. 6. Iterate through the hash map entries.

If a word has frequency exactly equal to 1, append it to the result list. 7. Return the result list.

Since the problem allows any order, no sorting is necessary.

Why it works

The algorithm works because the hash map stores the total number of occurrences of every word across both sentences combined.

A word is uncommon if and only if it appears exactly once globally. Any word with frequency greater than 1 either appears multiple times in one sentence or appears in both sentences. Therefore, selecting all words with frequency 1 guarantees correctness.

Python Solution

from typing import List
from collections import Counter

class Solution:
    def uncommonFromSentences(self, s1: str, s2: str) -> List[str]:
        words = s1.split() + s2.split()

        frequency = Counter(words)

        result = []

        for word, count in frequency.items():
            if count == 1:
                result.append(word)

        return result

The implementation begins by splitting both sentences into lists of words. These lists are concatenated into a single list called words.

The Counter class from Python's collections module automatically counts how many times each word appears. This is an ideal fit for the problem because it removes the need for manual frequency bookkeeping.

After building the frequency map, we iterate through every (word, count) pair. Whenever the count equals 1, we append the word to the result list.

Finally, the result list is returned.

The implementation is concise because Python provides built in tools for frequency counting, but the underlying logic directly follows the algorithm described earlier.

Go Solution

package main

import "strings"

func uncommonFromSentences(s1 string, s2 string) []string {
	words1 := strings.Split(s1, " ")
	words2 := strings.Split(s2, " ")

	frequency := make(map[string]int)

	for _, word := range words1 {
		frequency[word]++
	}

	for _, word := range words2 {
		frequency[word]++
	}

	result := []string{}

	for word, count := range frequency {
		if count == 1 {
			result = append(result, word)
		}
	}

	return result
}

The Go implementation follows the same overall strategy as the Python version.

Instead of using Python's Counter, Go uses a map[string]int to manually track frequencies. Each word increments its count in the map.

The result is stored in a slice of strings. Since Go slices are dynamic, appending uncommon words is straightforward.

There are no integer overflow concerns because the input size is extremely small. Also, returning an empty slice is perfectly valid if no uncommon words exist.

Worked Examples

Example 1

s1 = "this apple is sweet"
s2 = "this apple is sour"

After splitting:

Sentence	Words
s1	["this", "apple", "is", "sweet"]
s2	["this", "apple", "is", "sour"]

Combined words:

["this", "apple", "is", "sweet", "this", "apple", "is", "sour"]

Frequency map construction:

Word	Frequency
this	2
apple	2
is	2
sweet	1
sour	1

Now we collect words with frequency 1:

["sweet", "sour"]

Example 2

s1 = "apple apple"
s2 = "banana"

After splitting:

Sentence	Words
s1	["apple", "apple"]
s2	["banana"]

Combined words:

["apple", "apple", "banana"]

Frequency map:

Word	Frequency
apple	2
banana	1

Only "banana" has frequency 1.

Result:

["banana"]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each word is processed once while building the frequency map
Space	O(n)	The hash map may store every unique word

Here, n is the total number of words across both sentences.

The algorithm is linear because each word contributes a constant amount of work during insertion and lookup in the hash map. The extra space comes from storing frequency counts for all distinct words.

Test Cases

from typing import List

class Solution:
    def uncommonFromSentences(self, s1: str, s2: str) -> List[str]:
        from collections import Counter

        frequency = Counter(s1.split() + s2.split())

        return [word for word, count in frequency.items() if count == 1]

sol = Solution()

# Provided example 1
assert sorted(sol.uncommonFromSentences(
    "this apple is sweet",
    "this apple is sour"
)) == ["sour", "sweet"]

# Provided example 2
assert sorted(sol.uncommonFromSentences(
    "apple apple",
    "banana"
)) == ["banana"]

# Single unique word in each sentence
assert sorted(sol.uncommonFromSentences(
    "hello",
    "world"
)) == ["hello", "world"]

# Same word appears once in both sentences
assert sol.uncommonFromSentences(
    "apple",
    "apple"
) == []

# Repeated words in one sentence only
assert sorted(sol.uncommonFromSentences(
    "a a b",
    "c"
)) == ["b", "c"]

# No uncommon words
assert sol.uncommonFromSentences(
    "one one",
    "one"
) == []

# Multiple uncommon words
assert sorted(sol.uncommonFromSentences(
    "red blue green",
    "blue yellow"
)) == ["green", "red", "yellow"]

# Minimum size input
assert sorted(sol.uncommonFromSentences(
    "a",
    "b"
)) == ["a", "b"]

# Word repeated across sentences
assert sorted(sol.uncommonFromSentences(
    "cat dog",
    "dog bird"
)) == ["bird", "cat"]

# Repeated words in both sentences
assert sol.uncommonFromSentences(
    "x x y y",
    "z z"
) == []

Test	Why
`"this apple is sweet"` vs `"this apple is sour"`	Validates the main example
`"apple apple"` vs `"banana"`	Ensures repeated words are excluded
`"hello"` vs `"world"`	Tests two independent uncommon words
`"apple"` vs `"apple"`	Verifies shared words are excluded
`"a a b"` vs `"c"`	Tests duplicates within one sentence
`"one one"` vs `"one"`	Confirms no uncommon words case
`"red blue green"` vs `"blue yellow"`	Tests multiple valid uncommon words
`"a"` vs `"b"`	Validates smallest possible inputs
`"cat dog"` vs `"dog bird"`	Tests overlap across sentences
`"x x y y"` vs `"z z"`	Ensures all repeated words are removed

Edge Cases

Words repeated within the same sentence

A common mistake is to only check whether a word exists in the other sentence. However, a word repeated multiple times in the same sentence is not uncommon.

For example:

s1 = "apple apple"
s2 = "banana"

Even though "apple" does not appear in s2, it appears twice in s1, so it must not be included. The frequency map correctly handles this because "apple" gets count 2.

Words appearing once in both sentences

Another tricky case occurs when a word appears exactly once in each sentence.

Example:

s1 = "cat"
s2 = "cat"

The word "cat" appears twice globally, so it is not uncommon. The implementation correctly excludes it because its frequency becomes 2.

No uncommon words at all

Some inputs produce an empty result.