Reconstruct Original Digits from English - Practice Coding Problems

Reconstruct Original Digits from English - Problem

Given a string s containing an out-of-order English representation of digits 0-9, return the digits in ascending order.

The string contains English words for digits like "zero", "one", "two", etc., but the letters are jumbled together. Your task is to figure out which digits are present and return them sorted.

Note: Each digit appears at most once in the input string.

Input & Output

Example 1 — Basic Mixed Digits

$ Input: s = "owtzero"

› Output: "02"

💡 Note: The string contains letters for "zero" (z,e,r,o) and "two" (t,w,o). Since we need ascending order, return "02".

Example 2 — Single Digit

$ Input: s = "fviefuro"

› Output: "45"

💡 Note: Contains "four" (f,o,u,r) and "five" (f,i,v,e). The shared 'f' appears twice. Result is "45".

Example 3 — Multiple Overlapping

$ Input: s = "nnei"

› Output: "19"

💡 Note: Contains "one" (o,n,e) and "nine" (n,i,n,e). Both share 'n' and 'e', but the counts work out perfectly for digits 1 and 9.

Constraints

1 ≤ s.length ≤ 10⁵
s consists of lowercase English letters only
s contains an out-of-order representation of some digits 0-9
Each digit appears at most once

Visualization

Tap to expand

Understanding the Visualization

Input

Scrambled letters from English digit words

Process

Use letter frequency analysis to identify digits

Output

Digits in ascending order

Key Takeaway

🎯 Key Insight: Use unique letters as fingerprints - some digits have letters that appear in no other digit word

Asked in

G Google 23 f Facebook 18 M Microsoft 15

The key insight is recognizing that some digits have unique letters that appear nowhere else (z→zero, w→two, u→four, x→six, g→eight). Best approach uses frequency counting with strategic ordering to identify digits efficiently. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(2^10 × n)	O(1)	Generate all possible digit combinations and check if they match the letter count
Frequency Count with Unique Letters	O(n)	O(1)	Use unique letters as fingerprints to identify digits, then handle remaining digits
Optimized Pattern Recognition	O(n)	O(1)	Smart ordering of digit identification to minimize conflicts and dependencies

Brute Force - Try All Combinations — Algorithm Steps

Step 1: Generate all possible combinations of digits 0-9
Step 2: For each combination, convert digits to English words
Step 3: Count letters and compare with input string
Step 4: Return the matching combination in ascending order

Visualization

Tap to expand

Step-by-Step Walkthrough

Input Analysis

Count letter frequencies in the scrambled string

Generate Combinations

Try all possible digit subsets (2^10 = 1024 combinations)

Match & Return

Find combination that matches letter frequencies exactly

Code -

solution.c — C

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

char* solution(char* s) {
    char* words[] = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
    int inputCount[26] = {0};
    int len = strlen(s);
    
    for (int i = 0; i < len; i++) {
        inputCount[s[i] - 'a']++;
    }
    
    // Try all combinations
    for (int mask = 0; mask < 1024; mask++) {
        int totalCount[26] = {0};
        int digits[10];
        int digitCount = 0;
        
        for (int i = 0; i < 10; i++) {
            if (mask & (1 << i)) {
                digits[digitCount++] = i;
                int wordLen = strlen(words[i]);
                for (int j = 0; j < wordLen; j++) {
                    totalCount[words[i][j] - 'a']++;
                }
            }
        }
        
        int match = 1;
        for (int i = 0; i < 26; i++) {
            if (totalCount[i] != inputCount[i]) {
                match = 0;
                break;
            }
        }
        
        if (match) {
            // Sort digits
            for (int i = 0; i < digitCount - 1; i++) {
                for (int j = i + 1; j < digitCount; j++) {
                    if (digits[i] > digits[j]) {
                        int temp = digits[i];
                        digits[i] = digits[j];
                        digits[j] = temp;
                    }
                }
            }
            
            char* result = malloc(11 * sizeof(char));
            for (int i = 0; i < digitCount; i++) {
                result[i] = '0' + digits[i];
            }
            result[digitCount] = '\0';
            return result;
        }
    }
    
    char* result = malloc(1 * sizeof(char));
    result[0] = '\0';
    return result;
}

int main() {
    char s[1000];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    char* result = solution(s);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^10 × n)

2^10 combinations to try, each requiring O(n) letter counting

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables for counting

✓ Linear Space

31.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler