Uncommon Words from Two Sentences

Problem Statement

LeetCode-884: 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.

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

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

Approach

This is rather an easy question that we can solve using a frequency map. We can split the sentences into words and store the frequency of each word in a hashmap. Then we can iterate over the hashmap and check if the frequency of the word is 1 in either of the sentences. If the frequency is 1, then the word is uncommon and we can add it to the result.

Implementation

Here is a Java implementation of the approach:

public String[] uncommonFromSentences(String s1, String s2) {
    Map<String, Integer> freq = new HashMap<>();
    for(String str : s1.split(" ")){
        freq.put(str, freq.getOrDefault(str, 0) + 1);
    }

    for(String str : s2.split(" ")){
        freq.put(str, freq.getOrDefault(str, 0) + 1);
    }
    
    return freq.entrySet()
            .stream()
            .filter(entry -> entry.getValue() == 1)
            .map(entry -> entry.getKey())
            .toList()
            .toArray(new String[0]);
}

Complexity Analysis

The time complexity for this approach is $O(N)$ where $N$ is the total number of words in both sentences. The space complexity is also O(N) due to the hashmap used to store the frequency of each word.