884. Uncommon Words from Two Sentences - Explanation

Description

A word is uncommon if it occurs exactly once in one sentence and never in the other. Given the sentences s1 and s2, return all uncommon words in any order. Each sentence contains lowercase English words separated by single spaces, with no leading or trailing spaces.

Example 1:

Input: s1 = "red blue"
s2 = "red green"

Output: ["blue","green"]

Explanation: The word "red" occurs in both sentences, so it is excluded. "blue" and "green" each occur once overall and are uncommon.

Example 2:

Input: s1 = "cat cat"
s2 = "dog"

Output: ["dog"]

Explanation: "cat" appears twice in the first sentence and is excluded. "dog" appears once in the second sentence and never in the first, so it is the only uncommon word.

Example 3:

Input: s1 = "a b"
s2 = "b a"

Output: []

Explanation: Both "a" and "b" appear in both sentences. Neither word is uncommon, so return an empty array.

Constraints:

1 <= s1.length, s2.length <= 200
Both sentences contain only lowercase English letters and spaces.
Words are separated by one space, with no leading or trailing spaces.

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Hash Maps - Using dictionaries or hash maps to count frequencies of elements
String Manipulation - Splitting strings into words and iterating through them

1. Hash Map - I

Intuition

A word is uncommon if it appears exactly once across both sentences. We can combine both sentences and count the frequency of each word. Any word with a count of 1 is uncommon.

Algorithm

Split both sentences into words and combine them.
Use a hash map to count the frequency of each word.
Iterate through the hash map and collect all words with a count of 1.
Return the list of uncommon words.

class Solution:
    def uncommonFromSentences(self, s1: str, s2: str) -> List[str]:
        count = defaultdict(int)
        for w in s1.split(" ") + s2.split(" "):
            count[w] += 1

        res = []
        for w, cnt in count.items():
            if cnt == 1:
                res.append(w)
        return res

public class Solution {
    public String[] uncommonFromSentences(String s1, String s2) {
        String[] words = (s1 + " " + s2).split(" ");
        Map<String, Integer> count = new HashMap<>();

        for (String w : words) {
            count.put(w, count.getOrDefault(w, 0) + 1);
        }

        List<String> res = new ArrayList<>();
        for (Map.Entry<String, Integer> entry : count.entrySet()) {
            if (entry.getValue() == 1) {
                res.add(entry.getKey());
            }
        }

        return res.toArray(new String[0]);
    }
}

class Solution {
public:
    vector<string> uncommonFromSentences(string s1, string s2) {
        unordered_map<string, int> count;
        istringstream ss(s1 + " " + s2);
        string w;
        while (ss >> w) {
            count[w]++;
        }

        vector<string> res;
        for (auto& [word, freq] : count) {
            if (freq == 1) {
                res.push_back(word);
            }
        }

        return res;
    }
};

class Solution {
    /**
     * @param {string} s1
     * @param {string} s2
     * @return {string[]}
     */
    uncommonFromSentences(s1, s2) {
        const words = (s1 + ' ' + s2).split(' ');
        const count = new Map();

        for (const w of words) {
            count.set(w, (count.get(w) || 0) + 1);
        }

        const res = [];
        for (const [w, c] of count.entries()) {
            if (c === 1) {
                res.push(w);
            }
        }

        return res;
    }
}

public class Solution {
    public string[] UncommonFromSentences(string s1, string s2) {
        string[] words = (s1 + " " + s2).Split(' ');
        Dictionary<string, int> count = new Dictionary<string, int>();

        foreach (string w in words) {
            if (count.ContainsKey(w)) {
                count[w]++;
            } else {
                count[w] = 1;
            }
        }

        List<string> res = new List<string>();
        foreach (var entry in count) {
            if (entry.Value == 1) {
                res.Add(entry.Key);
            }
        }

        return res.ToArray();
    }
}

func uncommonFromSentences(s1 string, s2 string) []string {
    words := strings.Split(s1 + " " + s2, " ")
    count := make(map[string]int)

    for _, w := range words {
        count[w]++
    }

    res := []string{}
    for w, c := range count {
        if c == 1 {
            res = append(res, w)
        }
    }

    return res
}

class Solution {
    fun uncommonFromSentences(s1: String, s2: String): Array<String> {
        val words = "$s1 $s2".split(" ")
        val count = mutableMapOf<String, Int>()

        for (w in words) {
            count[w] = count.getOrDefault(w, 0) + 1
        }

        val res = mutableListOf<String>()
        for ((w, c) in count) {
            if (c == 1) {
                res.add(w)
            }
        }

        return res.toTypedArray()
    }
}

class Solution {
    func uncommonFromSentences(_ s1: String, _ s2: String) -> [String] {
        let words = (s1 + " " + s2).split(separator: " ").map { String($0) }
        var count = [String: Int]()

        for w in words {
            count[w, default: 0] += 1
        }

        var res = [String]()
        for (w, c) in count {
            if c == 1 {
                res.append(w)
            }
        }

        return res
    }
}

impl Solution {
    pub fn uncommon_from_sentences(s1: String, s2: String) -> Vec<String> {
        let mut count = HashMap::new();
        for w in s1.split(' ').chain(s2.split(' ')) {
            *count.entry(w).or_insert(0) += 1;
        }

        count.into_iter()
            .filter(|&(_, c)| c == 1)
            .map(|(w, _)| w.to_string())
            .collect()
    }
}

Time & Space Complexity

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

Where $n$ and $m$ are the lengths of the strings $s1$ and $s2$ , respectively.

2. Hash Map - II

Intuition

This is a more concise version of the same approach. We use built-in functions like Counter (in Python) or stream operations (in Java) to reduce boilerplate while maintaining the same logic.

Algorithm

Combine and split both sentences into words.
Count word frequencies using a built-in counter or grouping function.
Filter to keep only words with count equal to 1.
Return the filtered words.

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

public class Solution {
    public String[] uncommonFromSentences(String s1, String s2) {
        String[] words = (s1 + " " + s2).split(" ");
        Map<String, Integer> count = new HashMap<>();

        for (String w : words) {
            count.put(w, count.getOrDefault(w, 0) + 1);
        }

        return count.entrySet()
                    .stream()
                    .filter(e -> e.getValue() == 1)
                    .map(Map.Entry::getKey)
                    .toArray(String[]::new);
    }
}

class Solution {
public:
    vector<string> uncommonFromSentences(string s1, string s2) {
        unordered_map<string, int> count;
        istringstream ss(s1 + " " + s2);
        string w;
        while (ss >> w) {
            count[w]++;
        }

        vector<string> res;
        for (auto& [w, c] : count) {
            if (c == 1) {
                res.push_back(w);
            }
        }

        return res;
    }
};

class Solution {
    /**
     * @param {string} s1
     * @param {string} s2
     * @return {string[]}
     */
    uncommonFromSentences(s1, s2) {
        const words = (s1 + ' ' + s2).split(' ');
        const count = new Map();

        for (const w of words) {
            count.set(w, (count.get(w) || 0) + 1);
        }

        return [...count.entries()].filter(([_, c]) => c === 1).map(([w]) => w);
    }
}

public class Solution {
    public string[] UncommonFromSentences(string s1, string s2) {
        string[] words = (s1 + " " + s2).Split(' ');
        Dictionary<string, int> count = new Dictionary<string, int>();

        foreach (string w in words) {
            if (count.ContainsKey(w)) {
                count[w]++;
            } else {
                count[w] = 1;
            }
        }

        return count.Where(e => e.Value == 1)
                    .Select(e => e.Key)
                    .ToArray();
    }
}

func uncommonFromSentences(s1 string, s2 string) []string {
    words := strings.Split(s1 + " " + s2, " ")
    count := make(map[string]int)

    for _, w := range words {
        count[w]++
    }

    res := []string{}
    for w, c := range count {
        if c == 1 {
            res = append(res, w)
        }
    }

    return res
}

class Solution {
    fun uncommonFromSentences(s1: String, s2: String): Array<String> {
        val words = "$s1 $s2".split(" ")
        val count = words.groupingBy { it }.eachCount()

        return count.filter { it.value == 1 }
                    .keys
                    .toTypedArray()
    }
}

class Solution {
    func uncommonFromSentences(_ s1: String, _ s2: String) -> [String] {
        let words = (s1 + " " + s2).split(separator: " ").map { String($0) }
        var count = [String: Int]()

        for w in words {
            count[w, default: 0] += 1
        }

        return count.filter { $0.value == 1 }.map { $0.key }
    }
}

impl Solution {
    pub fn uncommon_from_sentences(s1: String, s2: String) -> Vec<String> {
        let mut count = HashMap::new();
        for w in s1.split(' ').chain(s2.split(' ')) {
            *count.entry(w).or_insert(0) += 1;
        }

        count.into_iter()
            .filter(|&(_, c)| c == 1)
            .map(|(w, _)| w.to_string())
            .collect()
    }
}

Time & Space Complexity

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

Where $n$ and $m$ are the lengths of the strings $s1$ and $s2$ , respectively.

Common Pitfalls

Misunderstanding "Uncommon" Definition

A word is uncommon if it appears exactly once across both sentences combined, not once per sentence. Some mistakenly check if a word appears in one sentence but not the other, which is incorrect. A word appearing twice in the same sentence is also not uncommon.

Incorrect String Splitting

When splitting sentences into words, be careful with edge cases like multiple spaces or empty strings. The problem guarantees single spaces between words, but forgetting to handle the concatenation properly (e.g., not adding a space between s1 and s2) can cause words at the boundary to merge incorrectly.