Uncommon Words from Two Sentences
EasyPrompt
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 <= 200s1ands2consist of lowercase English letters and spaces.s1ands2do not have leading or trailing spaces.- All the words in
s1ands2are separated by a single space.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves combining both sentences and then iterating through the list of words. For each word, a second, nested loop is used to count its total occurrences. If the count is exactly one, the word is considered uncommon. This method is straightforward but computationally expensive.
Algorithm
- Concatenate
s1ands2with a space in between to form a single string. - Split the combined string by spaces to get an array of all words.
- Initialize an empty list
resultto store the uncommon words. - Iterate through the array of words with an outer loop (let's say index
i). - For each word
words[i], start an inner loop (indexj) to iterate through the entire array again. - Inside the inner loop, count how many times
words[i]appears in the array. - After the inner loop finishes, if the count for
words[i]is 1, add it to theresultlist. - Finally, convert the
resultlist to a string array and return it.
Walkthrough
The core idea is to first create a single collection of all words from both sentences. Then, for every single word in this collection, we perform a full scan of the collection to count how many times it appears. A word is added to our final list of uncommon words only if its total count is exactly one. This brute-force check is performed for every word.
import java.util.ArrayList;import java.util.List; class Solution { public String[] uncommonFromSentences(String s1, String s2) { String[] words = (s1 + " " + s2).split(" "); List<String> result = new ArrayList<>(); for (int i = 0; i < words.length; i++) { int count = 0; for (int j = 0; j < words.length; j++) { if (words[i].equals(words[j])) { count++; } } if (count == 1) { // To avoid duplicates in the result list, we can check before adding if (!result.contains(words[i])) { result.add(words[i]); } } } return result.toArray(new String[0]); }}Note: The provided code can be slightly optimized by using a Set to store results to handle duplicates automatically, but the core O(L^2) complexity remains.
Complexity
Time
O(L^2 * W), where `L` is the total number of words in both sentences and `W` is the maximum length of a word. The nested loops cause the quadratic time complexity, and each string comparison takes O(W) time.
Space
O(L * W), where `L` is the total number of words and `W` is the maximum length of a word. This space is required to store the combined array of words and the result list.
Trade-offs
Pros
Simple to understand and implement without requiring knowledge of advanced data structures.
Cons
Very inefficient due to the O(L^2) time complexity, where L is the total number of words.
Will likely result in a 'Time Limit Exceeded' error for larger inputs.
A much more efficient approach is to use a hash map to count the frequency of each word across both sentences. The problem can be simplified to finding words that have a total count of exactly 1 when both sentences are considered together. By iterating through all words once to build the frequency map, we can then iterate through the map's entries to find words that appeared exactly once.
Algorithm
- Initialize a hash map,
wordCounts, to store words as keys and their frequencies as values (e.g.,Map<String, Integer>). - Split the first sentence
s1into words and iterate through them, updating their counts in thewordCountsmap. - Do the same for the second sentence
s2, updating the samewordCountsmap. - Initialize an empty list
resultto store the uncommon words. - Iterate through the entries of the
wordCountsmap. - For each entry, if the value (count) is 1, add the key (word) to the
resultlist. - Convert the
resultlist to a string array and return it.
Walkthrough
This optimal approach leverages a hash map for efficient counting. We first process all words from both sentences and store their frequencies in a single hash map. A word is mapped to its integer count. After counting all words, we perform a second pass, this time over the hash map itself. We collect all words for which the stored count is exactly 1. This avoids the expensive nested loops of the brute-force method.
import java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.Map; class Solution { public String[] uncommonFromSentences(String s1, String s2) { Map<String, Integer> wordCounts = new HashMap<>(); String combined = s1 + " " + s2; for (String word : combined.split(" ")) { wordCounts.put(word, wordCounts.getOrDefault(word, 0) + 1); } List<String> result = new ArrayList<>(); for (String word : wordCounts.keySet()) { if (wordCounts.get(word) == 1) { result.add(word); } } return result.toArray(new String[result.size()]); }}Complexity
Time
O(S1 + S2), where `S1` and `S2` are the lengths of the sentences. Splitting the strings, populating the hash map, and iterating through it all take time proportional to the total length of the input strings.
Space
O(U * W), where `U` is the number of unique words and `W` is the average length of a word. In the worst case, where all words are unique, this becomes O(S1 + S2), where S1 and S2 are the lengths of the input strings.
Trade-offs
Pros
Highly efficient with a linear time complexity.
Conceptually simple and easy to implement.
Scales well with the size of the input sentences.
Cons
Requires extra space to store the hash map, which can be proportional to the total length of the input sentences in the worst case.
Solutions
Solution
class Solution {public String[] uncommonFromSentences(String s1, String s2) { Map<String, Integer> cnt = new HashMap<>(); for (String s : s1.split(" ")) { cnt.put(s, cnt.getOrDefault(s, 0) + 1); } for (String s : s2.split(" ")) { cnt.put(s, cnt.getOrDefault(s, 0) + 1); } List<String> ans = new ArrayList<>(); for (var e : cnt.entrySet()) { if (e.getValue() == 1) { ans.add(e.getKey()); } } return ans.toArray(new String[0]); }}/** * @param {string} s1 * @param {string} s2 * @return {string[]} */ var uncommonFromSentences = function ( s1 , s2 ) { const cnt = new Map (); for ( const s of [... s1 . split ( ' ' ), ... s2 . split ( ' ' )]) { cnt . set ( s , ( cnt . get ( s ) || 0 ) + 1 ); } const ans = []; for ( const [ s , v ] of cnt . entries ()) { if ( v == 1 ) { ans . push ( s ); } } return ans ; };class Solution {public: vector<string> uncommonFromSentences(string s1, string s2) { unordered_map<string, int> cnt; auto add = [&](string &s) { stringstream ss(s); string w; while (ss >> w) ++cnt[move(w)]; }; add(s1); add(s2); vector<string> ans; for (auto &[s, v] : cnt) if (v == 1) ans.emplace_back(s); return ans; }};class Solution: def uncommonFromSentences(self, s1: str, s2: str) -> List[str]: cnt = Counter(s1 . split()) + Counter(s2 . split()) return [s for s, v in cnt . items() if v == 1]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.