Abstract / Summary

Find words that appear exactly once in total when combining two sentences and list them.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 76% (400k+ submissions).

Typical patterns to solve this problem:

• Counting
• Hash Table
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a method that extracts words appearing exactly once across two input sentences while excluding any word that appears in both. It builds frequency maps for each sentence, then iterates over those maps to emit the uncommon words as a generator. The design leverages Python’s defaultdict for concise counting and uses generator semantics to produce results lazily.

Step 1: Building a frequency map for the first sentence

freq1 = defaultdict(int)
for w in s1.split(" "):
    freq1[w] += 1

In this segment the code splits the first input string on spaces, iterating over each token. The defaultdict(int) automatically initializes missing keys to zero, allowing the count to be incremented directly. The result is a dictionary where each key is a word from the first sentence and the associated value is the number of times that word occurs.

Step 2: Building a frequency map for the second sentence

freq2 = defaultdict(int)
for w in s2.split(" "):
    freq2[w] += 1

The second sentence undergoes an identical counting process, producing a separate frequency dictionary. Maintaining two distinct maps preserves the ability to compare occurrences across the sentences without mutating a shared structure.

Step 3: Yielding words that are unique to one sentence

for f in freq1:
    if freq1[f] == 1 and f not in freq2:
        yield f
for f in freq2:
    if freq2[f] == 1 and f not in freq1:
        yield f

The method iterates over the keys of the first frequency map, checking two conditions: the word must appear exactly once in its own sentence (freq1[f] == 1) and must be absent from the other sentence’s map (f not in freq2). When both hold, the word is yielded. The same logic is applied to the second map, ensuring that uncommon words from both sides are emitted. Because the function uses yield, the caller receives a generator that produces results on demand rather than constructing an intermediate list.

Edge Cases Handled

The algorithm gracefully manages sentences that contain repeated words, as the frequency check (== 1) filters out any word occurring more than once in its own sentence. It also correctly handles words that appear in both sentences, because the presence test (f not in freq2 or f not in freq1) excludes any overlapping tokens. Empty strings are tolerated: splitting an empty string yields a list containing a single empty token, which is then counted; however, the subsequent uniqueness checks will prevent an empty token from being yielded unless it satisfies the strict uniqueness criteria. Leading, trailing, or multiple consecutive spaces produce empty string tokens as well, and those tokens are treated like any other word, ensuring consistent behavior regardless of spacing irregularities.

Performance Optimizations

The use of defaultdict(int) eliminates the need for explicit existence checks before incrementing counts, reducing branching overhead during the counting loops. Splitting each sentence once and iterating over the resulting list avoids repeated parsing. By storing frequencies in hash-based dictionaries, look-ups for existence (f not in freq2) and count retrieval (freq1[f]) execute in average constant time, keeping the overall processing linear with respect to the total number of words. The generator pattern (yield) avoids materializing the full result set in memory, which is advantageous when the caller consumes the output incrementally or when the combined set of uncommon words is large. This lazy evaluation also means that the method can be integrated into pipelines without incurring the cost of building an intermediate collection.

Imagine two lego towers made of letter blocks. Each tower is built from a sentence, where every individual word is like one block.

The code starts by looking at the first tower. It picks up every block one by one and counts how many times each type of block appears. It keeps this list of counts in a special box. Then it does the exact same thing for the second tower, putting those counts into another box.

After sorting everything out, the code goes through the first box to see if any block appears only once and is completely missing from the second tower. If a block is special that way, it gets set aside. Finally, the code checks the second box to see if any blocks there are also special by appearing just once and staying away from the first tower. All these unique blocks are collected as the final result.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java						TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python	JS	Java		Rust		Go		TS
	LeetcodeHelp	C++	Python		Java
	Progiez	C++	Python		Java
github	BigEggStudy					C#
	black-shadows	C++
	charles-wangkai				Java
	DimitrisJim									C
	everthis			JS
	fartem							Ruby
	fengvyi	C++
	halfrost								Go
	JoshCrozier			JS
	keineahnung2345	C++
	Krazune	C++
	lkwq007		Python
	lzl124631x	C++
	ruoru						Rust
	suxrobGM					C#
	varunu28				Java
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
fengvyi	C++
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C++
lkwq007	Python
lzl124631x	C++
ruoru	Rust
suxrobGM	C#
varunu28	Java
YuriSpiridonov	Python
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality