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.To solve #884 Uncommon Words from Two Sentences, the key idea is to track how often each word appears across both sentences. Start by splitting each sentence into individual words using spaces. Then use a hash table (or dictionary) to count the frequency of every word.
A word is considered uncommon if it appears exactly once in one sentence and does not appear in the other sentence. Practically, this means the word’s total frequency across both sentences is exactly 1. After building the frequency map, iterate through it and collect all words whose count equals 1.
This approach works efficiently because hash tables allow constant-time updates and lookups. If n and m are the number of words in the two sentences, counting and filtering can be done in linear time. The method is simple, readable, and commonly used in interview settings when dealing with word frequency problems.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Table Word Counting | O(n + m) | O(n + m) |
NeetCodeIO
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.
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.
1def uncommonFromSentences(s1, s2):
2 from collections import Counter
3 count1 = Counter(s1.split())
4 count2 = Counter(s2.split())
5 result = []
6
7 for word in count1:
8 if count1[word] == 1 and word not in count2:
9 result.append(word)
10 for word in count2:
11 if count2[word] == 1 and word not in count1:
12 result.append(word)
13
14 return resultFirst, 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.
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.
Time Complexity: O(n + m) merging and counting stages.
Space Complexity: O(n + m) for the storage of counts.
1import java.util.*;
2
3
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
A word is uncommon only if it appears exactly once in one sentence and does not appear in the other. By combining both sentences into a single frequency map, a valid uncommon word will have a total count of one.
Yes, variations of word frequency and hash table problems are common in coding interviews. This problem tests basic string processing, counting techniques, and familiarity with hash maps.
A hash table (or dictionary) is the best data structure for this problem. It allows fast insertion and lookup while counting word frequencies. This makes it efficient to identify words that appear exactly once.
The optimal approach is to use a hash table to count the frequency of every word across both sentences. After counting, return all words whose frequency is exactly one. This ensures the word appears once in one sentence and not at all in the other.
We create a map to hold word counts after merging both sentences, using split to create a word list. Words occurring once in total are collected into a result list.