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

1. Which English digit names contain a letter no other digit word has?
2. After you count those “unique” letters, remove their contribution and look for the next set of hints.
3. 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.

1. Build a frequency map of all letters in s.
2. Detect digits with truly unique letters:
   • 'z' → 0 (“zero”)
   • 'w' → 2 (“two”)
   • 'u' → 4 (“four”)
   • 'x' → 6 (“six”)
   • 'g' → 8 (“eight”)
3. 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
4. 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
5. 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