423. Reconstruct Original Digits from English - Detailed Explanation

Problem Statement

You’re given a non‑empty string s containing an out‑of‑order English representation of digits zero through nine. Each digit’s English word is concatenated, jumbled, and mixed with the others. Your task is to recover the original digits in ascending order.

Examples
1.

Input: s = "owoztneoer"
Output: "012"
Explanation: The letters can be rearranged to "onezero two", so the digits are [0,1,2].

Input: s = "fviefuro"
Output: "45"
Explanation: The letters can be rearranged to "five four", so the digits are [4,5].

Input: s = "zerozero"
Output: "00"
Explanation: Two copies of "zero".

Constraints

1 ≤ s.length ≤ 10⁵
s consists only of lowercase English letters.
It is guaranteed that s is a valid jumble of one or more digit words.

Hints

Which English digit names contain a letter no other digit word has?
After you count those “unique” letters, remove their contribution and look for the next set of hints.
You only need to tally letter frequencies once and do a constant‑time deduction for each digit.

Approach 1: Character‑Count with Unique Identifiers

This is the standard O(n) solution using the fact that some digit names have letters nobody else uses.

Build a frequency map of all letters in s.
Detect digits with truly unique letters:
- 'z' → 0 (“zero”)
- 'w' → 2 (“two”)
- 'u' → 4 (“four”)
- 'x' → 6 (“six”)
- 'g' → 8 (“eight”)
Subtract those counts from the global map (conceptually), then detect the next set:
- 'h' appears only in 3 (“three”) and 8; so count3 = freq['h'] − count8
- 'f' appears only in 5 (“five”) and 4; so count5 = freq['f'] − count4
- 's' appears only in 7 (“seven”) and 6; so count7 = freq['s'] − count6
Finally the remaining digits share more common letters:
- 'o' appears in 0,1,2,4 → count1 = freq['o'] − count0 − count2 − count4
- 'i' appears in 5,6,8,9 → count9 = freq['i'] − count5 − count6 − count8
Construct the output string by appending each digit d exactly countd times, in ascending order from 0 to 9.

Step‑by‑Step Example

Take s = "fviefuro":

Frequency map: f:2,v:1,i:1,e:1,u:1,r:1,o:1
Unique letters:
- count4 = freq['u'] = 1
- count2 = freq['w'] = 0
- count0 = freq['z'] = 0
- count6 = freq['x'] = 0
- count8 = freq['g'] = 0
Next:
- count5 = freq['f'] − count4 = 2−1 = 1
- count3 = freq['h'] − count8 = 0−0 = 0
- count7 = freq['s'] − count6 = 0−0 = 0
Last:
- count1 = freq['o'] − count0 − count2 − count4 = 1−0−0−1 = 0
- count9 = freq['i'] − count5 − count6 − count8 = 1−1−0−0 = 0
Only non‑zero counts are count4=1 and count5=1 → output “45”.

Complexity Analysis

Time: O(n) to count letters, plus O(1) work per digit (constant steps).
Space: O(1) extra (just a 26‑entry array for frequencies and a 10‑entry array for digit counts).

Python Code

Python3

. . . .

Java Code

Java

. . . .

Approach 2: Brute‑Force Removal (Inefficient)

You could try repeatedly matching every digit word against the remaining letters, removing matched letters one digit at a time. This ends up O(n·D) or worse (D = number of digit names) and can degrade to O(n²) in practice. It’s fine for tiny inputs but fails at 10⁵ length.

Common Mistakes

Counting overlapping letters too early (e.g. using 'h' before removing eight).
Forgetting to subtract previously counted digits when computing shared letters.
Building the final string in the wrong order, giving unsorted results.

Edge Cases

Input has multiple copies of the same digit (e.g. "zerozerozero" → "000").
All digits are those with unique identifiers (e.g. only zeros and twos).
Very long strings that stress performance—only the O(n) method passes.

Alternative Variations

Reconstructing words from a letter‑jumble in other languages.
Given the output digits, produce the lexicographically smallest original string of words.