Watch 10 video solutions for Uncommon Words from Two Sentences, a easy level problem involving Hash Table, String, Counting. This walkthrough by NeetCodeIO has 6,212 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |