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.
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]); }}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.