Code Implementation

from collections import Counter

class Solution:
    def uncommonFromSentences(self, s1: str, s2: str) -> list[str]:
        # Split both sentences into words
        words = s1.split() + s2.split()
        # Count occurrences of each word
        count = Counter(words)
        # Return words that appear exactly once
        return [word for word in count if count[word] == 1]
      

#include <vector>
#include <string>
#include <unordered_map>
#include <sstream>

using namespace std;

class Solution {
public:
    vector<string> uncommonFromSentences(string s1, string s2) {
        unordered_map<string, int> count;
        stringstream ss1(s1), ss2(s2);
        string word;
        while (ss1 >> word) count[word]++;
        while (ss2 >> word) count[word]++;
        vector<string> res;
        for (auto &p : count) {
            if (p.second == 1) res.push_back(p.first);
        }
        return res;
    }
};
      

import java.util.*;

class Solution {
    public String[] uncommonFromSentences(String s1, String s2) {
        Map<String, Integer> count = new HashMap<>();
        for (String w : (s1 + " " + s2).split(" ")) {
            count.put(w, count.getOrDefault(w, 0) + 1);
        }
        List<String> res = new ArrayList<>();
        for (String w : count.keySet()) {
            if (count.get(w) == 1) res.add(w);
        }
        return res.toArray(new String[0]);
    }
}
      

/**
 * @param {string} s1
 * @param {string} s2
 * @return {string[]}
 */
var uncommonFromSentences = function(s1, s2) {
    const count = {};
    for (const w of (s1 + ' ' + s2).split(' ')) {
        count[w] = (count[w] || 0) + 1;
    }
    return Object.keys(count).filter(w => count[w] === 1);
};
      

Problem Description

You are given two sentences as strings, s1 and s2. Each sentence consists of words separated by single spaces, with no leading or trailing spaces. Your task is to find all the words that are "uncommon" between the two sentences.

A word is considered uncommon if it appears exactly once in one of the sentences and does not appear in the other sentence at all. The result should be a list of all such words.

Constraints:

• Each sentence may contain lowercase English letters and spaces only.
• There may be zero or more uncommon words.
• Order of output does not matter.

Thought Process

To solve this problem, let's first understand what makes a word "uncommon." We need to identify words that appear only once in the combined set of both sentences. If a word is repeated or appears in both sentences, it's not uncommon.

One way to approach this is to first split both sentences into their individual words. Then, we can count how many times each word appears in the combined list of words from both sentences. Any word that appears exactly once in total is an "uncommon" word.

A brute-force way would be to check each word in both sentences, count its occurrences in both, and see if it meets the criteria. However, this would be inefficient. To optimize, we can use a hash map (dictionary) to count occurrences efficiently.

Solution Approach

We can break the solution into the following steps:

1. Split the Sentences: Convert both s1 and s2 into lists of words by splitting on spaces.
2. Combine the Words: Concatenate the two lists into a single list containing all words from both sentences.
3. Count Occurrences: Use a hash map (dictionary) to count how many times each word appears in the combined list.
4. Filter Uncommon Words: Loop through the hash map and collect all words that appear exactly once.
5. Return the Result: Output the list of uncommon words.

We use a hash map because it allows us to count word occurrences in linear time, and lookups are O(1). This is much more efficient than checking each word separately in both sentences.

Example Walkthrough

Let's take the example:
s1 = "apple banana apple"
s2 = "banana orange"

1. Split Sentences:
   • s1: ["apple", "banana", "apple"]
   • s2: ["banana", "orange"]
2. Combine Words:
   • ["apple", "banana", "apple", "banana", "orange"]
3. Count Occurrences:
   • "apple": 2
   • "banana": 2
   • "orange": 1
4. Filter Uncommon Words:
   • Only "orange" appears exactly once.
5. Result: ["orange"]

This process ensures that only words appearing exactly once in the union of both sentences are selected.

Time and Space Complexity

Brute-force Approach:
For each word in each sentence, count its occurrences in both sentences, which is O(N^2) where N is the total number of words.

Optimized Approach:

• Time Complexity: O(N), where N is the total number of words in both sentences. We split, combine, count, and filter all in linear time.
• Space Complexity: O(N), for storing the counts in the hash map.

Summary

The problem asks us to find words that are unique to one sentence and do not occur in the other. By leveraging a hash map to count all word occurrences from both sentences, we can efficiently filter out the uncommon words. This approach is elegant because it avoids nested loops and leverages the power of hash-based counting for optimal performance.