Watch 10 video solutions for Reconstruct Original Digits from English, a medium level problem involving Hash Table, Math, String. This walkthrough by Algorithms Made Easy has 5,856 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given a string s containing an out-of-order English representation of digits 0-9, return the digits in ascending order.
Example 1:
Input: s = "owoztneoer" Output: "012"
Example 2:
Input: s = "fviefuro" Output: "45"
Constraints:
1 <= s.length <= 105s[i] is one of the characters ["e","g","f","i","h","o","n","s","r","u","t","w","v","x","z"].s is guaranteed to be valid.Problem Overview: A string contains shuffled characters representing English words for digits zero through nine ("zero", "one", ..., "nine"). The task is to reconstruct the original digits in ascending order. Each character may appear multiple times, and every letter belongs to exactly one digit word.
Approach 1: Unique Character Mapping (O(n) time, O(1) space)
The key observation: several digit words contain letters that appear in no other digit word. For example, 'z' only appears in zero, 'w' only in two, 'u' only in four, 'x' only in six, and 'g' only in eight. Count characters using a hash table or frequency array. Each unique letter directly determines how many times that digit occurs. After resolving these digits, subtract their letters from the counts. This reveals secondary unique letters like 'h' (three after removing eight), 'f' (five after removing four), 's' (seven after removing six), 'o' (one after removing zero, two, four), and finally 'i' (nine after removing five, six, eight). Build the result by appending digits in sorted order. The algorithm scans the string once for counts and performs constant digit deductions, giving O(n) time and O(1) space.
Approach 2: Iterative Subtraction (O(n) time, O(1) space)
This method also starts with a character frequency array but removes digits step by step instead of computing them directly. Maintain the frequency of each letter from the input string. Repeatedly check whether the characters required for a digit word exist. When all letters for a digit (like "zero" or "two") are present, decrement those counts and record the digit. The order of checks matters; digits with distinctive letters should be processed first to avoid conflicts. This approach mirrors manual reconstruction and is easy to reason about but requires careful ordering of digit removal. Complexity remains linear because each character is subtracted a constant number of times.
Recommended for interviews: The Unique Character Mapping approach is what interviewers expect. It shows pattern recognition and efficient use of counting with a math-style deduction process. Iterative subtraction works but looks less elegant. Demonstrating the unique-letter insight signals strong problem-solving ability.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Unique Character Mapping | O(n) | O(1) | Best general solution. Uses unique letters to directly deduce digit counts. |
| Iterative Subtraction | O(n) | O(1) | Useful when implementing a straightforward frequency-removal simulation. |