Uncommon Words from Two Sentences - Solution & Explanation

Problem Overview: You receive two space-separated sentences s1 and s2. A word is considered uncommon if it appears exactly once in one sentence and does not appear in the other sentence. The task is to return all such uncommon words.

This problem is mostly about counting occurrences of words across two strings. Once you can quickly check how often each word appears, filtering uncommon words becomes straightforward. The typical solution uses a hash table to store frequencies and relies on simple string parsing.

Approach 1: Using Frequency Count (O(n) time, O(n) space)

Split both sentences into word arrays and count the frequency of every word using a hash map. Insert words from both sentences into the same map, incrementing the count each time a word appears. After processing all tokens, iterate through the map and collect the words whose frequency is exactly 1. These are the words that appear once across both sentences and therefore satisfy the definition of uncommon.

The key insight: if a word appears once in one sentence and zero times in the other, the combined frequency is 1. If it appears in both sentences or multiple times in one sentence, its count will be greater than 1 and should be ignored. This approach uses constant-time hash lookups and is the most direct implementation of frequency counting.

This solution runs in O(n) time where n is the total number of words across both sentences. Space complexity is O(n) for storing the frequency map.

Approach 2: Merging and Identifying Uniques (O(n) time, O(n) space)

Another approach keeps counts for each sentence separately, then merges the results. First, split both sentences and build two frequency maps: one for s1 and one for s2. Next, iterate through the first map and select words with frequency 1 that do not exist in the second map. Repeat the same logic for the second map against the first.

This approach explicitly enforces the problem definition: the word must appear once in one sentence and zero times in the other. Although slightly more verbose, it improves clarity because each condition is checked directly rather than inferred from a combined count.

Time complexity remains O(n) since each word is processed a constant number of times. Space complexity is O(n) due to the two hash maps storing word frequencies.

Recommended for interviews: The combined frequency map approach is what interviewers usually expect. It demonstrates comfort with hash-based counting and leads to clean O(n) time complexity. The separate-map merging approach is still valid and can help explain the definition of "uncommon" more explicitly, but the single map solution is shorter and easier to implement during interviews.