# Uncommon Words from Two Sentences
**Difficulty:** EASY
[External](https://leetcode.com/problems/uncommon-words-from-two-sentences)
Canonical: https://scaleengineer.com/dsa/problems/uncommon-words-from-two-sentences
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Hash Table, String
---
## 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**.

**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 <= 200`
* `s1` and `s2` consist of lowercase English letters and spaces.
* `s1` and `s2` do not have leading or trailing spaces.
* All the words in `s1` and `s2` are separated by a single space.

# Approaches
## Brute Force with Nested Loops
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.
**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.
**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.
### Explanation
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.

```java
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.*
### Algorithm
*   Concatenate `s1` and `s2` with 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 `result` to 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 (index `j`) 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 the `result` list.
*   Finally, convert the `result` list to a string array and return it.

## Single Pass with Hash Map
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.
**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.
**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.
### Explanation
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.

```java
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()]);
    }
}
```
### 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 `s1` into words and iterate through them, updating their counts in the `wordCounts` map.
*   Do the same for the second sentence `s2`, updating the same `wordCounts` map.
*   Initialize an empty list `result` to store the uncommon words.
*   Iterate through the entries of the `wordCounts` map.
*   For each entry, if the value (count) is 1, add the key (word) to the `result` list.
*   Convert the `result` list to a string array and return it.

# Solutions
### Java

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

```

### JavaScript

```javascript
/** * @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 ; };
```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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]

```