Uncommon Words from Two Sentences

easy hash map string counting

Problem

A sentence is a string of single-space separated words. 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.

Inputs1 = "this apple is sweet", s2 = "this apple is sour"

Output["sweet", "sour"]

Across both sentences combined, "sweet" and "sour" each occur exactly once; "this", "apple", "is" each occur twice.

s1 (words separated by spaces)

s2 (words separated by spaces)

def uncommon_from_sentences(s1, s2):
    count = {}
    for w in (s1 + " " + s2).split():
        count[w] = count.get(w, 0) + 1
    return [w for w, c in count.items() if c == 1]

function uncommonFromSentences(s1, s2) {
  const count = new Map();
  for (const w of (s1 + " " + s2).split(/\s+/)) {
    count.set(w, (count.get(w) || 0) + 1);
  }
  const res = [];
  for (const [w, c] of count) if (c === 1) res.push(w);
  return res;
}

class Solution {
    public String[] uncommonFromSentences(String s1, String s2) {
        Map<String, Integer> count = new HashMap<>();
        for (String w : (s1 + " " + s2).split(" ")) {
            count.merge(w, 1, Integer::sum);
        }
        List<String> res = new ArrayList<>();
        for (Map.Entry<String, Integer> e : count.entrySet())
            if (e.getValue() == 1) res.add(e.getKey());
        return res.toArray(new String[0]);
    }
}

vector<string> uncommonFromSentences(string s1, string s2) {
    unordered_map<string, int> count;
    istringstream in(s1 + " " + s2);
    string w;
    while (in >> w) count[w]++;
    vector<string> res;
    for (auto& p : count) if (p.second == 1) res.push_back(p.first);
    return res;
}

Explanation

A word is "uncommon" when it appears exactly once across both sentences combined. That phrasing is the key insight: if a word is unique in one sentence and missing from the other, its total count over both sentences is simply 1.

So instead of comparing the two sentences separately, we glue them together with s1 + " " + s2, split on spaces, and count every word in one shared frequency map called count.

After counting, the answer is every word whose total is exactly 1. A word appearing twice in one sentence, or once in each sentence, ends up with a count of 2 or more, so it is correctly excluded.

Example: s1 = "this apple is sweet", s2 = "this apple is sour". Combined counts are this:2, apple:2, is:2, sweet:1, sour:1. Only sweet and sour have count 1, so the answer is ["sweet", "sour"].

We touch each word a constant number of times, so the whole thing runs in one linear pass over the words.

Time: O(m + n) Space: O(m + n)