Reconstruct Original Digits from English - Solution & Explanation
Problem Statement
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"].sis guaranteed to be valid.
Approach Overview
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 1: Unique Character Mapping
This approach uses unique identifiers for each digit's word representation in the English language. By identifying letters present in only one digit's name, like 'z' in 'zero', we progressively remove identified digits from the input string. This allows easy recovery of digits based on the frequency of unique letters.
The solution uses a Counter to keep track of the occurrences of each character in the input string s. It exploits unique characters in the spelling of certain numbers (like 'z' in zero, 'w' in two, etc.) to determine the count of those numbers. After these numbers are found, the script uses overlapping characters to determine others and constructs the result.
Complexity
Time Complexity: O(n), where n is the length of the string s, since we iterate over the input string and perform constant-time operations using the Counter.
Space Complexity: O(1), as the count array and resultant digit storage both use fixed space not growing with input size.
Approach 2: Iterative Subtraction
In this approach, we iteratively subtract recognized digits from the current string until the string is fully reduced. This involves pattern matching for each unique digit using substring searches that account for unique spellings.
This C solution proceeds by implementing character frequency counting similar to former strategies. It builds the result string by appending known digits based on zero-indexed character discovery, leveraging array positions for fast access. Memory management is handled manually to construct a resultant char array.
Code
C
JavaScript
Complexity
Time Complexity: O(n) for analyzing the string and constructing the output.
Space Complexity: O(1) since it uses fixed-size data structures for all computational logic without dynamic extensive allocation.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Unique Character Mapping | Time Complexity: O(n), where n is the length of the string |
| Iterative Subtraction | Time Complexity: O(n) for analyzing the string and constructing the output. |
| Default Approach | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Reconstruct Original Digits from English | Live Coding with Explanation | Leetcode - 423 • Algorithms Made Easy • 6,476 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Reconstruct Original Digits from English easy or hard?
Reconstruct Original Digits from English Python/Java solution
How to solve Reconstruct Original Digits from English in O(n)?
What is the best approach for Reconstruct Original Digits from English?
Is Reconstruct Original Digits from English asked at Google/Amazon/Meta?
What data structure is used in Reconstruct Original Digits from English?
What is the time complexity of Reconstruct Original Digits from English?
Ready to solve this problem?
Practice Reconstruct Original Digits from English with our built-in code editor and test cases.
Practice on FleetCode