Uncommon Words from Two Sentences

Easy
1176.

Uncommon Words from Two Sentences

Uncommon Words from Two Sentences is an easy coding problem on strings, hash table and counting, asked in Amazon and Bloomberg interviews.

A sentence is a list of words separated by single spaces, where every word is made of lowercase letters.

Given two sentences s1 and s2, a word is uncommon when it appears exactly once in one of the sentences and does not appear in the other — in other words, it occurs exactly once across both sentences together.

Return all uncommon words in the order they appear when reading s1 first and then s2. Return an empty list if there are none.

Example 1

Input
s1 = "code kairo code", s2 = "kairo duel"
Output
["duel"]
Explanation
`code` appears twice in `s1`, `kairo` once in each sentence.

Example 2

Input
s1 = "fast fast", s2 = "fast"
Output
[]

Example 3

Input
s1 = "solve the bug", s2 = "hunt the bug today"
Output
["solve","hunt","today"]

Constraints

  • 1 <= s1.length, s2.length <= 200
  • s1 and s2 consist of lowercase English letters and spaces
  • s1 and s2 have no leading or trailing spaces
  • all words in s1 and s2 are separated by a single space
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s1
 * @param {string} s2
 * @return {string[]}
 */
var uncommonFromSentences = function(s1, s2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Uncommon Words from Two Sentences — Problem & Solution

Uncommon Words from Two Sentences solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Uncommon Words from Two Sentences is an easy coding problem on strings, hash table and counting, asked in Amazon and Bloomberg interviews.

  • Difficulty: Easy
  • Topics: Strings, Hash Table, Counting
  • Asked at: Amazon, Bloomberg
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A sentence is a list of words separated by single spaces, where every word is made of lowercase letters.

Given two sentences s1 and s2, a word is uncommon when it appears exactly once in one of the sentences and does not appear in the other — in other words, it occurs exactly once across both sentences together.

Return all uncommon words in the order they appear when reading s1 first and then s2. Return an empty list if there are none.

Example 1

Input: s1 = "code kairo code", s2 = "kairo duel"
Output: ["duel"]
Explanation: `code` appears twice in `s1`, `kairo` once in each sentence.

Example 2

Input: s1 = "fast fast", s2 = "fast"
Output: []

Example 3

Input: s1 = "solve the bug", s2 = "hunt the bug today"
Output: ["solve","hunt","today"]

Constraints

  • 1 <= s1.length, s2.length <= 200
  • s1 and s2 consist of lowercase English letters and spaces
  • s1 and s2 have no leading or trailing spaces
  • all words in s1 and s2 are separated by a single space

Hints for Uncommon Words from Two Sentences

  1. Hint 1

    Being uncommon only depends on how many times a word occurs in total.

  2. Hint 2

    Put the words of both sentences into one list and count each word.

  3. Hint 3

    Walk the combined list in order and keep the words whose count is exactly 1.

How to solve Uncommon Words from Two Sentences

"Once in one sentence and absent from the other" is the same as "exactly once across both", so the two sentences can be merged into one word list and counted.

Approach

  1. Split s1 and s2 on spaces and concatenate the word lists, s1's first.
  2. Count every word in a hash map.
  3. Scan the combined list in order and output each word whose count is 1.

Why it works

A word that appears twice in the same sentence, or once in each, has a total count of at least 2 and is excluded; a word with total count 1 appears in exactly one sentence exactly once, which is the definition. Each such word occurs once in the list, so scanning in order emits it once, at its position.

Complexity

  • Time — O(|s1| + |s2|)
  • Space — O(|s1| + |s2|)

Pitfalls

  • A word repeated inside one sentence is not uncommon even if the other sentence lacks it.
  • Count words, not characters — split on spaces first.
  • Keep the reading order (s1 then s2); iterating a hash map gives an unspecified order.

Reference solution

Python

from typing import List
from collections import Counter

def uncommonFromSentences(s1: str, s2: str) -> List[str]:
    words = s1.split() + s2.split()
    cnt = Counter(words)
    return [w for w in words if cnt[w] == 1]

Java

public static String[] uncommonFromSentences(String s1, String s2) {
    String[] words = (s1 + " " + s2).split(" ");
    Map<String, Integer> cnt = new HashMap<>();
    for (String w : words) cnt.merge(w, 1, Integer::sum);
    List<String> res = new ArrayList<>();
    for (String w : words) if (cnt.get(w) == 1) res.add(w);
    return res.toArray(new String[0]);
}

C++

vector<string> uncommonFromSentences(string s1, string s2) {
    vector<string> words;
    istringstream in1(s1 + " " + s2);
    string w;
    while (in1 >> w) words.push_back(w);
    unordered_map<string, int> cnt;
    for (const string& x : words) cnt[x]++;
    vector<string> res;
    for (const string& x : words) if (cnt[x] == 1) res.push_back(x);
    return res;
}

JavaScript

var uncommonFromSentences = function(s1, s2) {
    var words = s1.split(" ").concat(s2.split(" "));
    var cnt = new Map();
    for (var i = 0; i < words.length; i++) cnt.set(words[i], (cnt.get(words[i]) || 0) + 1);
    return words.filter(function(w) { return cnt.get(w) === 1; });
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets