Abstract / Summary

Given two strings, find the single character that appears in the second string but not in the first.

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 61% (1+ million submissions).

Typical patterns to solve this problem:

• Bit Manipulation
• Hash Table
• Sorting
• 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 solves the classic problem of finding the extra character that appears in string t but not in string s. It builds a frequency table for characters in the first string, adjusts the table with characters from the second string, and then scans the table for the entry whose count is non-zero. The character associated with that entry is returned as the answer.

Key Steps

The algorithm can be divided into three logical sections, each illustrated with a concise code excerpt.

Building the frequency map from the first string

unordered_map<char, int> freq;
for (auto c : s)
    freq[c]++;

In this phase each character from s increments its counter in the hash map freq. The map therefore holds the exact number of occurrences of every character present in s.

Balancing the map with characters from the second string

for (auto c : t)
    freq[c]--;

Here every character from t decrements the corresponding entry. Because t contains all characters of s plus one additional character, the net effect is that every character that appears the same number of times in both strings ends with a zero count, while the extra character ends with a count of -1.

Locating the non-zero entry and returning the result

for (auto f : freq)
    if (f.second != 0)
        return f.first;
return 0;

The final loop walks through the map entries. The first entry whose count differs from zero corresponds to the extra character, which is immediately returned. The fallback return 0; provides a default return value for completeness, although the problem guarantees the existence of an answer.

Edge Cases Handled

The code gracefully handles several boundary conditions without additional checks.

When s is an empty string, the first loop does not modify the map, and the second loop inserts a single entry for the sole character in t. The subsequent scan finds this entry with a count of -1 and returns the correct character.

If s and t contain repeated characters, the increment and decrement operations correctly cancel matching occurrences. For example, with s = "aa" and t = "aaa", the map will hold {'a': -1} after processing both strings, and the algorithm will return 'a'.

The use of an unordered_map automatically accommodates any ASCII character, including non-alphabetic symbols, digits, and whitespace. The algorithm does not rely on any assumptions about character ordering or range.

Performance Optimizations

The implementation leverages a hash table (unordered_map) to achieve constant-time average updates for both insertion and lookup. By performing a single pass over each input string, the algorithm avoids nested iterations and thus scales linearly with the total length of the inputs.

The decision to decrement counts directly while iterating over t eliminates the need for a separate subtraction phase or an additional data structure. This in-place adjustment reduces memory overhead to the size of the distinct character set rather than the length of the strings.

Finally, the early return inside the final loop ensures that the function exits as soon as the extra character is identified, preventing unnecessary traversal of the remaining map entries. This short-circuit behavior can be beneficial when the extra character appears early in the internal bucket ordering of the hash map.

Imagine you have two boxes of alphabet magnets. The first box has a collection of letters, and the second box has the exact same letters but with one extra magnet hidden inside. Finding that extra magnet is just like playing a game of matching. You start by going through the first box and making a little tally mark for every letter you find so you know exactly what is there. After that, you go through the second box and erase one tally mark for every letter you see. Once you finish looking at both boxes, almost every letter you counted will have its marks wiped away completely because there were pairs for them. The one letter that still has a mark left over is the secret extra magnet that was added into the mix. You simply spot the letter that did not find its match and point to it.

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		Java		Go	C	Rust		TS
	LeetcodeHelp	C++	Python		Java
	Progiez	C++	Python		Java
github	BigEggStudy			C#
	black-shadows	C++
	chandansgowda		Python
	charles-wangkai				Java
	chenyanzhe	C++
	DimitrisJim							C
	everthis					JS
	fartem									Ruby
	halfrost						Go
	haoel	C++
	JoshCrozier					JS
	keineahnung2345	C++
	Krazune			C#
	linouk23	C++
	lkwq007		Python
	muhammadfarhankt						Go
	qiyuangong				Java
	ruoru								Rust
	shreymehul			C#
	suxrobGM			C#
	trung-hn		Python
	varunu28				Java
	vli02							C
	XiaotaoGuo	C++
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C, C++, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
chandansgowda	Python
charles-wangkai	Java
chenyanzhe	C++
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C#
linouk23	C++
lkwq007	Python
muhammadfarhankt	Go
qiyuangong	Java
ruoru	Rust
shreymehul	C#
suxrobGM	C#
trung-hn	Python
varunu28	Java
vli02	C
XiaotaoGuo	C++
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