423. Reconstruct Original Digits from English - Solution

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

The problem

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.

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.

Python

from collections import Counter

def originalDigits(s):
    count = Counter(s)
    output = [0] * 10
    
    output[0] = count['z']
    output[2] = count['w']
    output[4] = count['u']
    output[6] = count['x']
    output[8] = count['g']
    
    output[1] = count['o'] - output[0] - output[2] - output[4]
    output[3] = count['h'] - output[8]
    output[5] = count['f'] - output[4]
    output[7] = count['s'] - output[6]
    output[9] = count['i'] - output[5] - output[6] - output[8]
    
    result = ''
    for i in range(10):
        result += str(i) * output[i]
    return result

Java

import java.util.*;

public class OriginalDigits {
    public String originalDigits(String s) {
        int[] count = new int[26 + (int)'a'];
        for (char c : s.toCharArray()) {
            count[c]++;
        }
        
        int[] output = new int[10];
        output[0] = count['z'];
        output[2] = count['w'];
        output[4] = count['u'];
        output[6] = count['x'];
        output[8] = count['g'];
 
        output[1] = count['o'] - output[0] - output[2] - output[4];
        output[3] = count['h'] - output[8];
        output[5] = count['f'] - output[4];
        output[7] = count['s'] - output[6];
        output[9] = count['i'] - output[5] - output[6] - output[8];

        StringBuilder result = new StringBuilder();
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < output[i]; j++) {
                result.append(i);
            }
        }
        return result.toString();
    }
}

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.

Try this approach in the editor

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.

JavaScript

function originalDigits(s) {
    const count = new Array(26).fill(0);
    for (let i = 0; i < s.length; i++) {
        count[s.charCodeAt(i) - 'a'.charCodeAt(0)]++;
    }

    const output = new Array(10).fill(0);
    output[0] = count['z'.charCodeAt(0) - 'a'.charCodeAt(0)];
    output[2] = count['w'.charCodeAt(0) - 'a'.charCodeAt(0)];
    output[4] = count['u'.charCodeAt(0) - 'a'.charCodeAt(0)];
    output[6] = count['x'.charCodeAt(0) - 'a'.charCodeAt(0)];
    output[8] = count['g'.charCodeAt(0) - 'a'.charCodeAt(0)];

    output[1] = count['o'.charCodeAt(0) - 'a'.charCodeAt(0)] - output[0] - output[2] - output[4];
    output[3] = count['h'.charCodeAt(0) - 'a'.charCodeAt(0)] - output[8];
    output[5] = count['f'.charCodeAt(0) - 'a'.charCodeAt(0)] - output[4];
    output[7] = count['s'.charCodeAt(0) - 'a'.charCodeAt(0)] - output[6];
    output[9] = count['i'.charCodeAt(0) - 'a'.charCodeAt(0)] - output[5] - output[6] - output[8];

    let result = '';
    for (let i = 0; i < 10; i++) {
        result += i.toString().repeat(output[i]);
    }
    return result;
}

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char* originalDigits(char* s) {
    int count[26] = {0};
    for (int i = 0; i < strlen(s); ++i) {
        count[s[i] - 'a']++;
    }

    int output[10] = {0};
    output[0] = count['z' - 'a'];
    output[2] = count['w' - 'a'];
    output[4] = count['u' - 'a'];
    output[6] = count['x' - 'a'];
    output[8] = count['g' - 'a'];

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

    char* result = (char*)malloc(100);
    int pos = 0;
    for (int i = 0; i < 10; ++i) {
        for (int j = 0; j < output[i]; ++j) {
            result[pos++] = '0' + i;
        }
    }
    result[pos] = '\0';
    return result;
}

JavaScript utilizes a similar logic with a combination of array handling for character frequency. Using straightforward subtraction logic to manipulate counts ensures each digit is accurately represented. The char encoding aids in efficient array index mapping without explicit enumerations.

Complexity

Time Complexity: O(n), with simple loop and space management.
Space Complexity: O(1), adhering to minimal space use for character and digit management.

Try this approach in the editor

Approach 3: Default Approach

C++

class Solution {
public:
    string originalDigits(string s) {
        vector<int> counter(26);
        for (char c : s) ++counter[c - 'a'];
        vector<int> cnt(10);
        cnt[0] = counter['z' - 'a'];
        cnt[2] = counter['w' - 'a'];
        cnt[4] = counter['u' - 'a'];
        cnt[6] = counter['x' - 'a'];
        cnt[8] = counter['g' - 'a'];

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

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

        string ans;
        for (int i = 0; i < 10; ++i)
            for (int j = 0; j < cnt[i]; ++j)
                ans += char(i + '0');
        return ans;
    }
};

func originalDigits(s string) string {
	counter := make([]int, 26)
	for _, c := range s {
		counter[c-'a']++
	}
	cnt := make([]int, 10)
	cnt[0] = counter['z'-'a']
	cnt[2] = counter['w'-'a']
	cnt[4] = counter['u'-'a']
	cnt[6] = counter['x'-'a']
	cnt[8] = counter['g'-'a']

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

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

	ans := []byte{}
	for i, c := range cnt {
		ans = append(ans, bytes.Repeat([]byte{byte('0' + i)}, c)...)
	}
	return string(ans)
}

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 `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.
Iterative Subtraction	Time Complexity: O(n), with simple loop and space management. Space Complexity: O(1), adhering to minimal space use for character and digit management.
Default Approach	–

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.

Frequently asked questions

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.

Reconstruct Original Digits from English solution and explanation

The problem

Approach overview

Approach 1: Unique Character Mapping

Approach 2: Iterative Subtraction

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Reconstruct Original Digits from English solution and explanation

The problem

Approach overview

Approach 1: Unique Character Mapping

Approach 2: Iterative Subtraction

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems