Abstract / Summary

Given a string of words for digits zero to nine, determine the count of each digit in the original number.

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 53% (100k+ submissions).

Typical patterns to solve this problem:

• Hash Table
• Math
• 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 implementation reconstructs the original numeric digits from a jumbled string that contains the English words for the digits zero through nine. It relies on the fact that certain letters appear uniquely in the spelling of specific digits. By counting characters once and then extracting digit frequencies in a deterministic order, the algorithm produces the digits in ascending order as a concatenated string.

Character Frequency Collection

The first phase builds a histogram of all characters in the input string.

freq = defaultdict(int)
for c in s:
    freq[c] += 1

A single linear scan populates freq, guaranteeing that each character is accounted for exactly once.

Extracting Digits Using Unique Markers

The core logic proceeds through the digits in an order where each step can rely on a letter that is unique to the remaining unresolved digits. For each digit, the count is taken directly from the frequency of its unique marker, and the frequencies of all letters that compose the word are decremented accordingly.

Zero

zero = freq["z"]
freq["e"] -= zero
freq["r"] -= zero
freq["o"] -= zero

The presence of 'z' can only belong to the word “zero”, so its count determines the number of zeros.

Two

two = freq["w"]
freq["t"] -= two
freq["o"] -= two

The letter 'w' uniquely identifies “two”.

Four

four = freq["u"]
freq["f"] -= four
freq["o"] -= four
freq["r"] -= four

'u' appears only in “four”.

Six

six = freq["x"]
freq["s"] -= six
freq["i"] -= six

'x' is exclusive to “six”.

Three

three = freq["r"]
freq["t"] -= three
freq["h"] -= three
freq["e"] -= 2 * three

After removing zero, two, and four, the remaining 'r' belongs to “three”.

Five

five = freq["f"]
freq["i"] -= five
freq["v"] -= five
freq["e"] -= five

At this point 'f' can only arise from “five”.

Seven

seven = freq["v"]
freq["s"] -= seven
freq["e"] -= 2 * seven
freq["n"] -= seven

'v' now uniquely maps to “seven”.

Eight

eight = freq["t"]
freq["e"] -= eight
freq["i"] -= eight
freq["g"] -= eight
freq["h"] -= eight

The remaining 't' corresponds to “eight”.

Nine

nine = freq["i"]
freq["n"] -= 2 * nine
freq["e"] -= nine

After previous deductions, 'i' signals “nine”.

One

one = freq["o"]
freq["n"] -= one
freq["e"] -= one

Finally, any leftover 'o' belongs to “one”.

At the end of this sequence, all entries in freq are reduced to zero, confirming that every character has been accounted for.

Constructing the Result

The algorithm builds the output by repeating each digit character according to the computed count and concatenating them in numeric order.

result = ""
result += "0" * zero
result += "1" * one
result += "2" * two
result += "3" * three
result += "4" * four
result += "5" * five
result += "6" * six
result += "7" * seven
result += "8" * eight
result += "9" * nine
return result

String multiplication provides an efficient way to generate the required repetitions without explicit loops.

Edge Cases Handled

When the input string is empty, the initial frequency map contains no entries, all digit counts resolve to zero, and the final result is an empty string.

If the input contains multiple instances of the same digit word, the unique-letter extraction correctly aggregates the count because each occurrence contributes the same unique marker.

When the input includes all ten digits in any order, the cascade of deductions ensures that each digit’s count is isolated without interference, leaving a clean zeroed frequency map.

The algorithm also tolerates strings where letters appear in a highly interleaved fashion; the reliance on unique markers guarantees correct identification regardless of ordering.

Performance Optimizations

The solution performs a single pass to build the character histogram, avoiding repeated scans of the input.

All subsequent operations are simple arithmetic updates on the frequency dictionary, which are O(1) per digit.

String construction leverages Python’s built-in multiplication, which is implemented in C and runs faster than manual concatenation loops.

By ordering the digit extraction to use unique letters first, the code minimizes the number of adjustments needed for overlapping letters, reducing the total number of dictionary updates.

Overall, the approach achieves a tight constant factor in its runtime, making it well-suited for large input strings.

Imagine a giant pile of mixed-up letters from a bunch of number words like zero, one, and two. The first thing that happens is sorting all these letters into little bins so that every letter has a place to live. Once the letters are in their bins, the code starts a fun detective game.

It looks for letters that are very special because they only appear in one number word. For example, the letter z only shows up in zero, so whenever a z is found, the computer knows it must be part of a zero. After counting that zero, it carefully takes away all the letters belonging to that word from the bins. By doing this over and over for each number, it clears away the letters one number at a time like solving a puzzle. After all the detective work is done and the bins are finally empty, the code puts all the numbers together in the right order from zero to nine to show what was hidden in the starting pile.

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
	LeetcodeHelp	C++	Python	Java
	Progiez	C++	Python	Java
github	black-shadows	C++
	charles-wangkai			Java
	everthis				JS
	fsq	C++
	gouthampradhan			Java
	halfrost							Go
	JoshCrozier				JS
	linouk23	C++
	lkwq007		Python
	lzl124631x	C++
	ruoru					Rust
	suxrobGM								C#
	trung-hn		Python
	varunu28			Java
	wisdompeak	C++
	yuanliu666						Kotlin
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
gouthampradhan	Java
halfrost	Go
JoshCrozier	JavaScript
linouk23	C++
lkwq007	Python
lzl124631x	C++
ruoru	Rust
suxrobGM	C#
trung-hn	Python
varunu28	Java
wisdompeak	C++
yuanliu666	Kotlin
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