# Reconstruct Original Digits from English
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/reconstruct-original-digits-from-english)
Canonical: https://scaleengineer.com/dsa/problems/reconstruct-original-digits-from-english
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Hash Table, String
**Companies:** [Wix](https://scaleengineer.com/companies/wix), [Salesforce](https://scaleengineer.com/companies/salesforce), [NetApp](https://scaleengineer.com/companies/netapp)
---
## 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 <= 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.

# Approaches
## Backtracking Search
This approach frames the problem as finding the correct count for each digit (0-9) that accounts for all characters in the input string. It uses a recursive backtracking algorithm to explore all possible combinations of digit counts.
**Time:** O(K^10 * L) where K is the maximum possible count for any single digit, and L is the alphabet size (26). The recursion depth is 10, and at each level, we can branch up to K times. This is exponential and too slow for the given constraints. · **Space:** O(1). The recursion depth is constant (10), and at each level, we store a character count array of constant size (26).
**Pros:** It's a general approach that could work for similar problems where a direct counting trick isn't obvious.
**Cons:** Extremely inefficient due to its exponential time complexity.; Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints.; More complex to implement correctly compared to the optimal solution.
### Explanation
First, we count the frequency of each character in the input string `s`. We then define a recursive function, say `backtrack(digit, counts)`, which tries to determine the number of occurrences for the current `digit`. The function iterates through all possible counts for the current `digit`, from 0 up to the maximum possible (limited by the available characters in `counts`). For each possible count, it subtracts the corresponding characters from the `counts` map and makes a recursive call for the next digit (`digit + 1`). If a recursive call returns `true` (meaning a valid combination was found for the subsequent digits), it means we've found a solution. We store the count for the current digit and also return `true`. The base case for the recursion is when we have considered all digits (i.e., `digit == 10`). At this point, if all character counts are zero, we have successfully reconstructed the original digits. Once the backtracking process successfully finds the counts for all digits, we construct the final string.

```java
class Solution {
    // Word representations for digits 0-9
    String[] words = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
    // Character counts for each word
    int[][] wordCharCounts = new int[10][26];
    // Resulting digit counts
    int[] digitCounts = new int[10];

    public String originalDigits(String s) {
        // Pre-calculate character counts for each digit word
        for (int i = 0; i < 10; i++) {
            for (char c : words[i].toCharArray()) {
                wordCharCounts[i][c - 'a']++;
            }
        }

        // Count characters in the input string
        int[] sCounts = new int[26];
        for (char c : s.toCharArray()) {
            sCounts[c - 'a']++;
        }

        // Start backtracking from digit 0
        if (backtrack(0, sCounts)) {
            StringBuilder result = new StringBuilder();
            for (int i = 0; i < 10; i++) {
                for (int j = 0; j < digitCounts[i]; j++) {
                    result.append(i);
                }
            }
            return result.toString();
        }
        return ""; // Should not happen based on problem constraints
    }

    private boolean backtrack(int digit, int[] currentCounts) {
        if (digit == 10) {
            // Base case: check if all characters have been used
            for (int count : currentCounts) {
                if (count != 0) {
                    return false;
                }
            }
            return true;
        }

        // Determine max possible count for the current digit's word
        int maxCount = Integer.MAX_VALUE;
        for (int i = 0; i < 26; i++) {
            if (wordCharCounts[digit][i] > 0) {
                maxCount = Math.min(maxCount, currentCounts[i] / wordCharCounts[digit][i]);
            }
        }

        // Iterate through all possible counts for the current digit
        for (int i = 0; i <= maxCount; i++) {
            int[] nextCounts = new int[26];
            System.arraycopy(currentCounts, 0, nextCounts, 0, 26);
            for (int j = 0; j < 26; j++) {
                nextCounts[j] -= i * wordCharCounts[digit][j];
            }
            
            digitCounts[digit] = i;
            if (backtrack(digit + 1, nextCounts)) {
                return true;
            }
        }
        
        return false;
    }
}
```
### Algorithm
*   Create a frequency map `charCounts` for the characters in `s`.
*   Create an array `digitCounts` of size 10 to store the result.
*   Define a recursive function `backtrack(digit, currentCounts)`:
    *   **Base Case:** If `digit == 10`, check if all values in `currentCounts` are 0. If yes, a solution is found, return `true`; otherwise, return `false`.
    *   Determine the word for the current `digit`.
    *   Calculate the maximum possible number of times (`maxCount`) this word can be formed from `currentCounts`.
    *   Loop `i` from 0 to `maxCount`:
        *   Set `digitCounts[digit] = i`.
        *   Create `nextCounts` by subtracting characters for `i` copies of the word from `currentCounts`.
        *   If `backtrack(digit + 1, nextCounts)` returns `true`, then a solution is found down this path, so return `true`.
    *   If the loop completes, no solution was found for this branch. Return `false`.
*   Initiate the process with `backtrack(0, charCounts)`.
*   If it returns `true`, build the result string from `digitCounts` by appending each digit the required number of times in ascending order.

## Counting with Unique Character Identifiers
This approach leverages the fact that some digits have unique characters in their English spelling. By identifying these unique characters, we can determine the counts of certain digits directly. We can then use these counts to deduce the counts of other digits in a specific, carefully chosen order.
**Time:** O(N), where N is the length of the input string `s`. The initial character counting takes O(N). The subsequent calculations of digit counts take constant time, O(1). Building the final string takes time proportional to the number of digits, which is at most N. Therefore, the overall complexity is linear. · **Space:** O(1). We use a constant amount of extra space for the character counts array (size 26) and the digit counts array (size 10). The space for the result string is not counted as auxiliary space.
**Pros:** Highly efficient with linear time complexity.; Simple to implement and understand.; Guaranteed to find the correct solution due to the unique properties of the English spellings of digits.
**Cons:** This approach is very specific to this particular problem and the English language. It's not a general-purpose algorithm.
### Explanation
The key insight is to find an order of identification for the digits 0-9. We first count the frequency of all characters in the input string `s`. We observe that some characters uniquely identify a digit:
*   'z' appears only in "zero".
*   'w' appears only in "two".
*   'u' appears only in "four".
*   'x' appears only in "six".
*   'g' appears only in "eight".
This allows us to immediately determine the counts of digits 0, 2, 4, 6, and 8. After accounting for the characters used by these digits, we can find characters that are now unique for the remaining digits.
*   'h' appears in "three" and "eight". Since we know the count of "eight", we can find the count of "three".
*   'f' appears in "five" and "four". We can find the count of "five".
*   's' appears in "seven" and "six". We can find the count of "seven".
Finally, we can determine the counts of the last remaining digits, 'one' and 'nine', using characters like 'o' or 'i' and subtracting the counts from digits we've already solved. Once we have the counts of all ten digits, we build the result string by appending each digit the required number of times in ascending order.

```java
class Solution {
    public String originalDigits(String s) {
        // Step 1: Count character frequencies
        int[] charCounts = new int[26];
        for (char c : s.toCharArray()) {
            charCounts[c - 'a']++;
        }

        // Step 2: Create an array to store digit counts
        int[] digitCounts = new int[10];

        // Step 3: Calculate counts based on unique characters
        // Unique characters: z, w, u, x, g
        digitCounts[0] = charCounts['z' - 'a']; // "zero"
        digitCounts[2] = charCounts['w' - 'a']; // "two"
        digitCounts[4] = charCounts['u' - 'a']; // "four"
        digitCounts[6] = charCounts['x' - 'a']; // "six"
        digitCounts[8] = charCounts['g' - 'a']; // "eight"

        // Step 4: Calculate counts for digits that can now be identified
        // 'h' in "three" and "eight"
        digitCounts[3] = charCounts['h' - 'a'] - digitCounts[8];
        // 'f' in "five" and "four"
        digitCounts[5] = charCounts['f' - 'a'] - digitCounts[4];
        // 's' in "seven" and "six"
        digitCounts[7] = charCounts['s' - 'a'] - digitCounts[6];

        // Step 5: Calculate remaining digit counts
        // 'i' in "nine", "five", "six", "eight"
        digitCounts[9] = charCounts['i' - 'a'] - digitCounts[5] - digitCounts[6] - digitCounts[8];
        // 'o' in "one", "zero", "two", "four"
        digitCounts[1] = charCounts['o' - 'a'] - digitCounts[0] - digitCounts[2] - digitCounts[4];

        // Step 6: Build the result string
        StringBuilder result = new StringBuilder();
        for (int i = 0; i <= 9; i++) {
            for (int j = 0; j < digitCounts[i]; j++) {
                result.append(i);
            }
        }
        
        return result.toString();
    }
}
```
### Algorithm
*   Create a frequency map `charCounts` (an array of size 26) for the characters in the input string `s`.
*   Create an array `digitCounts` of size 10, initialized to zero, to store the final counts of each digit.
*   Calculate digit counts based on unique characters in a specific order:
    *   `digitCounts[0] = charCounts['z' - 'a']`
    *   `digitCounts[2] = charCounts['w' - 'a']`
    *   `digitCounts[4] = charCounts['u' - 'a']`
    *   `digitCounts[6] = charCounts['x' - 'a']`
    *   `digitCounts[8] = charCounts['g' - 'a']`
*   Calculate counts for digits that can now be uniquely identified:
    *   `digitCounts[3] = charCounts['h' - 'a'] - digitCounts[8]`
    *   `digitCounts[5] = charCounts['f' - 'a'] - digitCounts[4]`
    *   `digitCounts[7] = charCounts['s' - 'a'] - digitCounts[6]`
*   Calculate the remaining digit counts:
    *   `digitCounts[1] = charCounts['o' - 'a'] - digitCounts[0] - digitCounts[2] - digitCounts[4]`
    *   `digitCounts[9] = charCounts['i' - 'a'] - digitCounts[5] - digitCounts[6] - digitCounts[8]`
*   Create a `StringBuilder`.
*   Iterate from `i = 0` to `9`. For each `i`, append the character `(char)('0' + i)` to the `StringBuilder` `digitCounts[i]` times.
*   Return the `StringBuilder`'s string representation.

# Solutions
### Java

```java
class Solution { public String originalDigits ( String s ) { int [] counter = new int [ 26 ]; for ( char c : s . toCharArray ()) { ++ counter [ c - 'a' ]; } int [] cnt = new 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 ]; StringBuilder sb = new StringBuilder (); for ( int i = 0 ; i < 10 ; ++ i ) { for ( int j = 0 ; j < cnt [ i ]; ++ j ) { sb . append ( i ); } } return sb . toString (); } }
```

### CPP

```cpp
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 ; } };
```

### Python

```python
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 ))
```