Problem

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.

Examples

Example 1:

1
2
3
4

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:

1
2

Input: s1 = "apple apple", s2 = "banana"
Output: ["banana"]

Solution

Method 1 - Using Hashtable

  1. Combining Sentences: Combine both sentences s1 and s2 into a single string separated by a space.
  2. Counting Words: Use a HashMap to count the occurrences of each word.
  3. Filtering Uncommon Words: Iterate through the counted words and collect those that appear exactly once.
  4. Returning the Result: Return the list of words that meet the criteria.

Video explanation

Here is the video explaining this method in detail. Please check it out:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

public class Solution {
    public String[] uncommonFromSentences(String s1, String s2) {
        // Combine both sentences into one
        String combined = s1 + " " + s2;

        // Use a HashMap to count the occurrences of each word
        HashMap<String, Integer> count = new HashMap<>();
        for (String word : combined.split(" ")) {
            count.put(word, count.getOrDefault(word, 0) + 1);
        }

        // Gather all words that appear exactly once
        List<String> ans = new ArrayList<>();
        for (Map.Entry<String, Integer> entry : count.entrySet()) {
            if (entry.getValue() == 1) {
                ans.add(entry.getKey());
            }
        }

        return ans.toArray(new String[0]);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def uncommonFromSentences(self, s1: str, s2: str) -> List[str]:
        # Combine both sentences into one
        combined = s1 + " " + s2

        # Use a Counter to count the occurrences of each word
        count = Counter(combined.split())

        # Gather all words that appear exactly once
        return [word for word, freq in count.items() if freq == 1]

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)