LeetCode 423 - Reconstruct Original Digits from English

Difficulty: 🟡 Medium
Topics: Hash Table, Math, String

Solution

Problem Understanding

The problem asks us to reconstruct digits from a jumbled string of English letters representing numbers from 0 to 9. The input string s contains only characters from the set ["e","g","f","i","h","o","n","s","r","u","t","w","v","x","z"], which correspond to the letters used in English words for digits ("zero", "one", "two", etc.). The order of the letters in the input is arbitrary, and some letters may appear multiple times if digits are repeated.

The expected output is a string containing all digits present in the input, sorted in ascending numerical order. For example, if s = "owoztneoer", the letters can be rearranged to form "one", "zero", and "two", so the output should be "012".

The constraints tell us the input can be very long (1 <= s.length <= 10^5), but it is guaranteed to be valid, meaning every letter contributes to a valid digit. Edge cases to consider include strings where all letters correspond to a single digit, strings where digits repeat many times, and the smallest input length of 1.

Approaches

A brute-force approach would attempt to generate all permutations of the input letters and match them against the words "zero" through "nine". This guarantees correctness since it checks every possible arrangement, but it is computationally infeasible because the factorial growth of permutations is too large for the upper limit of s.length = 10^5.

The optimal approach leverages the observation that some digits contain letters that are unique to their English representation. For example, z only appears in "zero", w only appears in "two", u only in "four", x only in "six", and g only in "eight". By counting these unique letters first, we can determine how many of these digits appear. After handling these, the remaining digits can be deduced by subtracting letters already accounted for. This approach avoids permutations entirely and reduces the problem to counting letters and simple arithmetic.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n!)	O(n!)	Generates all permutations and matches against digit words. Infeasible for large input.
Optimal	O(n)	O(1)	Counts letters, identifies digits by unique markers, subtracts accounted letters, sorts results.

Algorithm Walkthrough

Initialize a frequency map of characters in the input string s. This allows quick lookup of how many times each letter appears.
Identify digits that have unique letters: "z" → 0, "w" → 2, "u" → 4, "x" → 6, "g" → 8. Count occurrences of these letters and store the corresponding number of digits.
Handle the remaining digits using letters that appear in multiple digits, subtracting letters already accounted for:

"h" appears in "three" and "eight", so the count of 3 is count(h) - count(8).
"f" appears in "five" and "four", so the count of 5 is count(f) - count(4).
"s" appears in "seven" and "six", so the count of 7 is count(s) - count(6).
"o" appears in "one", "zero", "two", and "four", so the count of 1 is count(o) - count(0) - count(2) - count(4).
"i" appears in "nine", "five", "six", and "eight", so the count of 9 is count(i) - count(5) - count(6) - count(8).

Create a result string by repeating each digit the number of times it appears, in ascending order.
Return the resulting string.

Why it works: By identifying digits with unique letters first, we establish a baseline count for several digits. The remaining digits can be uniquely determined by subtracting counts of already processed digits. This ensures each letter is accounted for exactly once, guaranteeing the correct reconstruction.

Python Solution

from collections import Counter

class Solution:
    def originalDigits(self, s: str) -> str:
        count = Counter(s)
        out = {}

        out[0] = count['z']
        out[2] = count['w']
        out[4] = count['u']
        out[6] = count['x']
        out[8] = count['g']

        out[3] = count['h'] - out[8]
        out[5] = count['f'] - out[4]
        out[7] = count['s'] - out[6]
        out[1] = count['o'] - out[0] - out[2] - out[4]
        out[9] = count['i'] - out[5] - out[6] - out[8]

        result = ''.join(str(i) * out[i] for i in range(10))
        return result

The Python code first counts all letters using Counter. Unique letters allow immediate identification of digits 0, 2, 4, 6, and 8. Subsequent digits are computed by removing the influence of already accounted digits. Finally, the output is constructed in ascending order by repeating each digit according to its frequency.

Go Solution

func originalDigits(s string) string {
    count := make(map[rune]int)
    for _, ch := range s {
        count[ch]++
    }

    out := make([]int, 10)
    out[0] = count['z']
    out[2] = count['w']
    out[4] = count['u']
    out[6] = count['x']
    out[8] = count['g']

    out[3] = count['h'] - out[8]
    out[5] = count['f'] - out[4]
    out[7] = count['s'] - out[6]
    out[1] = count['o'] - out[0] - out[2] - out[4]
    out[9] = count['i'] - out[5] - out[6] - out[8]

    result := ""
    for i := 0; i <= 9; i++ {
        for j := 0; j < out[i]; j++ {
            result += string(rune('0' + i))
        }
    }
    return result
}

The Go implementation mirrors Python closely, using a map[rune]int for the frequency count. Slices are used for storing digit counts, and string concatenation is used to assemble the final output. There are no nil issues because maps in Go return zero for missing keys.

Worked Examples

Example 1: "owoztneoer"

Step	Count Map	Digits Calculated	Explanation
Initial	{'o':3,'w':1,'z':1,'t':1,'n':1,'e':2,'r':1}	0,2,4,6,8	`z`=1 → 0, `w`=1 → 2, `u`=0 → 4, `x`=0 → 6, `g`=0 → 8
Remaining	same	3,5,7,1,9	`h`=0-0=0 →3, `f`=0-0=0 →5, `s`=0-0=0 →7, `o`=3-1-1-0=1 →1, `i`=0 →9
Result	-	"012"	Combine digits in order

Example 2: "fviefuro"

Step	Count Map	Digits Calculated	Explanation
Initial	{'f':2,'v':1,'i':1,'e':2,'u':1,'r':1,'o':1}	0,2,4,6,8	`u`=1 →4, others 0
Remaining	same	3,5,7,1,9	`f`=2-1=1 →5, `i`=1-1-0-0=0 →9, `o`=1-0-0-1=0 →1, `h`=0-0=0 →3, `s`=0-0=0 →7
Result	-	"45"	Combine digits in order

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Count letters in O(n), compute digits in O(1), build result in O(n)
Space	O(1)	Count map has at most 26 keys, digit array has 10 slots, both constant space relative to n

The main work is scanning the string once and then assembling the final output. The fixed-size maps make space usage independent of input length.

Test Cases

# Basic examples
assert Solution().originalDigits("owoztneoer") == "012"  # Example 1