A sentence is a string of single-space separated words where each word consists only of lowercase letters.
A word is uncommon if it appears exactly once in one of the sentences, and does not appear in the other sentence.
Given two sentences s1 and s2, return a list of all the uncommon words. You may return the answer in any order.
Example 1:
Input: s1 = "this apple is sweet", s2 = "this apple is sour"
Output: ["sweet","sour"]
Explanation:
The word "sweet" appears only in s1, while the word "sour" appears only in s2.
Example 2:
Input: s1 = "apple apple", s2 = "banana"
Output: ["banana"]
Constraints:
1 <= s1.length, s2.length <= 200s1 and s2 consist of lowercase English letters and spaces.s1 and s2 do not have leading or trailing spaces.s1 and s2 are separated by a single space.Problem Overview: You receive two space-separated sentences s1 and s2. A word is considered uncommon if it appears exactly once in one sentence and does not appear in the other sentence. The task is to return all such uncommon words.
This problem is mostly about counting occurrences of words across two strings. Once you can quickly check how often each word appears, filtering uncommon words becomes straightforward. The typical solution uses a hash table to store frequencies and relies on simple string parsing.
Approach 1: Using Frequency Count (O(n) time, O(n) space)
Split both sentences into word arrays and count the frequency of every word using a hash map. Insert words from both sentences into the same map, incrementing the count each time a word appears. After processing all tokens, iterate through the map and collect the words whose frequency is exactly 1. These are the words that appear once across both sentences and therefore satisfy the definition of uncommon.
The key insight: if a word appears once in one sentence and zero times in the other, the combined frequency is 1. If it appears in both sentences or multiple times in one sentence, its count will be greater than 1 and should be ignored. This approach uses constant-time hash lookups and is the most direct implementation of frequency counting.
This solution runs in O(n) time where n is the total number of words across both sentences. Space complexity is O(n) for storing the frequency map.
Approach 2: Merging and Identifying Uniques (O(n) time, O(n) space)
Another approach keeps counts for each sentence separately, then merges the results. First, split both sentences and build two frequency maps: one for s1 and one for s2. Next, iterate through the first map and select words with frequency 1 that do not exist in the second map. Repeat the same logic for the second map against the first.
This approach explicitly enforces the problem definition: the word must appear once in one sentence and zero times in the other. Although slightly more verbose, it improves clarity because each condition is checked directly rather than inferred from a combined count.
Time complexity remains O(n) since each word is processed a constant number of times. Space complexity is O(n) due to the two hash maps storing word frequencies.
Recommended for interviews: The combined frequency map approach is what interviewers usually expect. It demonstrates comfort with hash-based counting and leads to clean O(n) time complexity. The separate-map merging approach is still valid and can help explain the definition of "uncommon" more explicitly, but the single map solution is shorter and easier to implement during interviews.
In this approach, we compute the frequency of each word in both sentences. We then check for words that appear exactly once in one sentence and do not appear in the other sentence. This can be efficiently achieved by using hash maps (or dictionaries) to store these frequencies.
First, we split each of the sentences into words and count the occurrences using the Counter class from the collections module. We then iterate over these counts and check for words that meet our uncommon criteria. These words are collected in a result list.
Python
JavaScript
Time Complexity: O(n + m), where n and m are the lengths of s1 and s2 respectively, due to splitting and counting.
Space Complexity: O(n + m) due to storage for hash maps.
This approach involves merging both sentences into one list of words, along with a source identifier to track which sentence they came from. By counting occurrences in this merged list, we can determine uncommon words.
We merge the two sentences into one using a stream to count each word's occurrence, identifying those that appear only once. Since these unique words have a count of 1, they are the uncommon words across both sentences.
Time Complexity: O(n + m) merging and counting stages.
Space Complexity: O(n + m) for the storage of counts.
According to the problem description, as long as a word appears once, it meets the requirements of the problem. Therefore, we use a hash table cnt to record all words and their occurrence counts.
Then we traverse the hash table, and take out all strings that appear only once.
The time complexity is O(m + n), and the space complexity is O(m + n). Here, m and n are the lengths of strings s1 and s2, respectively.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| Approach | Complexity |
|---|---|
| Using Frequency Count | Time Complexity: O(n + m), where n and m are the lengths of s1 and s2 respectively, due to splitting and counting. Space Complexity: O(n + m) due to storage for hash maps. |
| Merging and Identifying Uniques | Time Complexity: O(n + m) merging and counting stages. Space Complexity: O(n + m) for the storage of counts. |
| Hash Table | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Frequency Count with Single Hash Map | O(n) | O(n) | Best general solution. Minimal code and efficient hash lookups. |
| Separate Maps and Merge Uniques | O(n) | O(n) | Useful when you want to explicitly track counts per sentence. |
Uncommon Words from Two Sentences - Leetcode 884 - Python • NeetCodeIO • 6,212 views views
Watch 9 more video solutions →Practice Uncommon Words from Two Sentences with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor