# LeetCode 884: Uncommon Words from Two Sentences

## Problem Restatement

We are given two sentences, `s1` and `s2`.

A word is uncommon if it satisfies both conditions:

1. It appears exactly once in one sentence.
2. It does not appear in the other sentence.

Return all uncommon words. The answer may be returned in any order. LeetCode defines each sentence as lowercase words separated by single spaces.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Two strings `s1` and `s2` |
| Output | List of uncommon words |
| Word format | Lowercase English letters |
| Sentence format | Words separated by one space |
| Order | Any order is accepted |

Function shape:

```python
def uncommonFromSentences(self, s1: str, s2: str) -> list[str]:
    ...
```

## Examples

Example 1:

```text
Input: s1 = "this apple is sweet", s2 = "this apple is sour"
Output: ["sweet", "sour"]
```

The combined word counts are:

| Word | Count |
|---|---:|
| `this` | 2 |
| `apple` | 2 |
| `is` | 2 |
| `sweet` | 1 |
| `sour` | 1 |

Only `sweet` and `sour` appear exactly once.

Example 2:

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

The word `apple` appears twice, so it is not uncommon.

The word `banana` appears exactly once, so it is uncommon.

## First Thought: Compare Two Sets

A first idea is to split both sentences into words and compare sets.

For example:

```python
set(s1.split()) ^ set(s2.split())
```

This finds words that appear in one sentence but not the other.

But it loses frequency information.

For:

```text
s1 = "apple apple"
s2 = "banana"
```

the set-based result would include `apple`, because `apple` appears only in `s1`.

That is wrong. `apple` appears twice, so it is not uncommon.

We need counts, not just membership.

## Key Insight

A word is uncommon exactly when it appears once in the combined list of words from both sentences.

So we can combine the words from both sentences, count each word, and return the words with count `1`.

This works because:

| Case | Combined Count | Uncommon? |
|---|---:|---|
| Appears once in `s1`, zero times in `s2` | 1 | Yes |
| Appears zero times in `s1`, once in `s2` | 1 | Yes |
| Appears once in both sentences | 2 | No |
| Appears multiple times in one sentence | 2 or more | No |

## Algorithm

Split both sentences into words.

Create a frequency table.

For each word in both sentences:

```python
count[word] += 1
```

Then return every word whose count is exactly `1`.

## Walkthrough

Use:

```text
s1 = "this apple is sweet"
s2 = "this apple is sour"
```

Combined words:

```text
this, apple, is, sweet, this, apple, is, sour
```

Frequency table:

| Word | Count |
|---|---:|
| `this` | 2 |
| `apple` | 2 |
| `is` | 2 |
| `sweet` | 1 |
| `sour` | 1 |

Words with count `1`:

```text
sweet, sour
```

Return:

```python
["sweet", "sour"]
```

## Correctness

The algorithm counts every word occurrence in both sentences.

For any word `w`, its count in the frequency table is the total number of times `w` appears across `s1` and `s2`.

If `count[w] == 1`, then `w` appears exactly once across both sentences. Therefore, it appears exactly once in one sentence and zero times in the other sentence. This is exactly the definition of an uncommon word.

If `count[w] != 1`, then either `w` does not appear, appears in both sentences, or appears more than once in one sentence. In all such cases, `w` is not uncommon.

The algorithm returns exactly the words whose count is `1`, so it returns exactly all uncommon words.

## Complexity

Let:

```text
m = len(s1)
n = len(s2)
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(m + n)` | We split and count all characters and words once |
| Space | `O(m + n)` | The frequency table may store all distinct words |

## Implementation

```python
from collections import Counter

class Solution:
    def uncommonFromSentences(self, s1: str, s2: str) -> list[str]:
        words = s1.split() + s2.split()
        count = Counter(words)

        return [word for word, freq in count.items() if freq == 1]
```

## Code Explanation

We split both sentences:

```python
words = s1.split() + s2.split()
```

The problem guarantees single spaces, but `split()` is still the cleanest way to get words.

Then we count every word:

```python
count = Counter(words)
```

Finally, we collect words that appear exactly once:

```python
return [word for word, freq in count.items() if freq == 1]
```

The returned order does not matter because the problem allows any order.

## Testing

```python
def run_tests():
    s = Solution()

    assert sorted(s.uncommonFromSentences(
        "this apple is sweet",
        "this apple is sour"
    )) == ["sour", "sweet"]

    assert s.uncommonFromSentences(
        "apple apple",
        "banana"
    ) == ["banana"]

    assert sorted(s.uncommonFromSentences(
        "one two three",
        "four five six"
    )) == ["five", "four", "one", "six", "three", "two"]

    assert s.uncommonFromSentences(
        "same",
        "same"
    ) == []

    assert sorted(s.uncommonFromSentences(
        "a b b",
        "c d d"
    )) == ["a", "c"]

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Shared common words | Only unique words remain |
| Duplicate in one sentence | Duplicate word is excluded |
| No overlap | Every single-occurrence word is uncommon |
| Same one-word sentence | No uncommon words |
| Duplicates in both sentences | Only words with total count `1` remain |