Is Reconstruct Original Digits from English easy or hard?

The problem is rated Medium because the implementation is simple but the key insight is recognizing unique letters that identify certain digits. Without this observation, brute-force reconstruction becomes complicated. Once the mapping is known, the solution becomes a straightforward frequency-counting problem.

Reconstruct Original Digits from English Python/Java solution

In Python or Java, create an array counting occurrences of each letter. Use the unique-letter rules (z, w, u, x, g) to determine digits 0, 2, 4, 6, and 8 first, then compute the remaining digits by subtracting overlaps. Finally append digits according to their counts to build the sorted result string.

How to solve Reconstruct Original Digits from English in O(n)?

Count the frequency of every character in the string. Use letters that uniquely identify digits such as 'z' for zero, 'w' for two, 'u' for four, 'x' for six, and 'g' for eight to determine their counts. Subtract those letters from the frequency table and derive remaining digits using letters like 'h', 'f', 's', 'o', and 'i'. Finally output digits in sorted order.

What is the best approach for Reconstruct Original Digits from English?

The best approach uses unique character mapping with a frequency hash table. Certain letters uniquely identify digits (for example 'z' → zero, 'w' → two, 'u' → four). Counting these letters reveals digit frequencies directly, and remaining digits can be deduced after subtracting overlaps. This solution runs in O(n) time with constant space.

Is Reconstruct Original Digits from English asked at Google/Amazon/Meta?

Digit reconstruction and character frequency deduction problems appear in interviews at companies like Google and Amazon. The question tests string manipulation, counting with hash tables, and logical deduction using unique identifiers. Variants may involve reconstructing sequences from scrambled representations.

What data structure is used in Reconstruct Original Digits from English?

The main data structure is a hash table or fixed-size frequency array storing counts of each character. This structure allows constant-time updates and lookups while deducting digit words. The algorithm also uses a small array to store counts for digits 0 through 9.

What is the time complexity of Reconstruct Original Digits from English?

The optimal solution runs in O(n) time where n is the length of the input string. The algorithm scans the string once to build a frequency count and performs a constant number of digit deductions. Space complexity is O(1) because only a fixed-size array for 26 letters and 10 digits is required.

Description Solution Video 5:27

423. Reconstruct Original Digits from English

Medium53.4% acceptance4 companies

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 <= 10⁵
s[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.

Asked at 4 companies

NetApp Kickdrum Wix

Google

Topics

5:27

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def originalDigits(self, s: str) -> str:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

"owoztneoer"

Input

"fviefuro"

Your code is saved on this device.Solution