#423

Medium

LeetCode Problem Workspace

Reconstruct Original Digits from English

This problem asks you to reconstruct digits from an out-of-order English string using hash counting and mathematical deduction techniques efficiently.

hash table math string

Problem Statement

Given a string containing scrambled English words representing digits from 0 to 9, your task is to determine the original digits and return them in ascending order. Each digit word may appear multiple times, and letters can be intermixed arbitrarily.

For example, if the input string is "owoztneoer", it contains letters forming "zero", "one", and "two". Your function should return the string "012" representing the digits in order. Similarly, input "fviefuro" should return "45". All inputs are guaranteed to be valid, and the output must list digits with no separators.

Examples

Example 1

Input: s = "owoztneoer"

Output: "012"

Example details omitted.

Example 2

Input: s = "fviefuro"

Output: "45"

Example details omitted.

Constraints

1 <= s.length <= 105
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.

Solution Approach

Count Letter Frequencies Using Hash Table

Create a hash table to tally the frequency of each character in the string. This allows O(1) lookups for each letter and forms the basis for identifying digits by unique characters like 'z' for zero or 'w' for two.

Identify Digits with Unique Letters and Deduce Others

Certain digits have letters that appear only in their word (e.g., 'z' for zero, 'x' for six). Count these first, then subtract their occurrences from overlapping letters to deduce remaining digits, applying simple arithmetic to resolve conflicts.

Assemble and Sort Digits

Once all digit counts are determined, generate the final string by repeating each digit according to its count. Sort digits in ascending order to meet the output requirement. This approach ensures correctness despite letter scrambling.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) where n is the length of the input string, dominated by single-pass counting and deductions. Space complexity is O(1) since the hash table size is fixed at 26 letters and digit counts are constant.

What Interviewers Usually Probe

Asks if you can optimize letter counting rather than trying all permutations of words.
Wants you to identify unique characters that map directly to digits before resolving overlaps.
Checks if you can handle edge cases where multiple digits share letters, like 'one' and 'nine'.

Common Pitfalls or Variants

Common pitfalls

Failing to deduct overlapping letters after counting unique digits leads to incorrect counts.
Sorting the final digits incorrectly or omitting digits present multiple times.
Assuming all letters are unique to one digit without checking overlaps, which causes errors.

Follow-up variants

Input strings with repeated digit words appearing multiple times, testing counting accuracy.
Strings missing some digits entirely, requiring robust handling of zeros in counts.
Extended character sets with additional noise letters not part of digit words, testing filtering.

FAQ

What is the key insight for reconstructing original digits from English letters?

The main insight is to count letter frequencies, use unique letters to identify certain digits first, then mathematically deduce the remaining digits from overlaps.

How do I handle letters that appear in multiple digit words?

Subtract counts of already-identified digits from overlapping letters to resolve which remaining digits they represent.

What data structure is best for counting letters efficiently?

A fixed-size hash table or array of 26 elements allows O(1) lookup per character and avoids repeated scans.

Do I need to sort the digits at the end?

Yes, after counting all digits, output them in ascending order as required by the problem.

Is this problem classified under any specific pattern?

Yes, it is a Hash Table plus Math pattern, combining frequency counting with arithmetic deduction to reconstruct digits.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def originalDigits(self, s: str) -> str:
        counter = Counter(s)
        cnt = [0] * 10

        cnt[0] = counter['z']
        cnt[2] = counter['w']
        cnt[4] = counter['u']
        cnt[6] = counter['x']
        cnt[8] = counter['g']

        cnt[3] = counter['h'] - cnt[8]
        cnt[5] = counter['f'] - cnt[4]
        cnt[7] = counter['s'] - cnt[6]

        cnt[1] = counter['o'] - cnt[0] - cnt[2] - cnt[4]
        cnt[9] = counter['i'] - cnt[5] - cnt[6] - cnt[8]

        return ''.join(cnt[i] * str(i) for i in range(10))

Continue Practicing

#166 fraction to recurring decimal #770 basic calculator iv #13 roman to integer