Problem Description

You are given a string s that contains a jumbled concatenation of the English words for digits zero through nine (e.g., "zero", "one", ..., "nine"), possibly repeated and in any order. Your task is to reconstruct and return the original digits in ascending order as a string.

• Each letter in s belongs to exactly one digit word.
• There is exactly one valid solution for every input.
• You must not reuse any letter more than once.
• Return the digits as a string in increasing order (e.g., "012").

Example:
Input: s = "owoztneoer"
Output: "012"

Thought Process

At first glance, the problem seems to require finding all possible combinations of digit words that could form the input string. A brute-force approach would try every possible combination of digit words and check if their concatenation matches s. However, this would be extremely inefficient due to the exponential number of possibilities.

Looking deeper, we notice that certain letters only appear in specific digit words. For example, the letter 'z' only appears in "zero", and 'w' only in "two". These unique letters can serve as anchors to identify the presence and count of those digits directly. Once we account for digits with unique letters, we can use a process of elimination to deduce the remaining digits.

The key is to count the frequency of each letter, use unique letters to identify some digits, and adjust the counts accordingly for overlapping letters in other digit words.

Solution Approach

We solve the problem by leveraging the unique letters in certain digit words and systematically reducing the letter counts. Here's a step-by-step breakdown:

1. Count All Letters:
   • Use a hash map (dictionary) to count the frequency of each letter in s. This allows O(1) lookups and updates.
2. Identify Digits with Unique Letters:
   • Certain digits have letters that appear in no other digit word:
   • 'z' → "zero" (0)
   • 'w' → "two" (2)
   • 'u' → "four" (4)
   • 'x' → "six" (6)
   • 'g' → "eight" (8)
   • For each unique letter, the count of that letter tells us how many times the corresponding digit occurs.
3. Remove Used Letters:
   • After identifying a digit, subtract its word's letters from the total counts, multiplied by how many times the digit occurs.
4. Identify Remaining Digits:
   • Now, some digits can be uniquely identified because their distinguishing letters are no longer shared:
   • 'o' → "one" (1) (after 0, 2, 4 removed)
   • 'h' → "three" (3) (after 8 removed)
   • 'f' → "five" (5) (after 4 removed)
   • 's' → "seven" (7) (after 6 removed)
   • 'i' → "nine" (9) (after 5, 6, 8 removed)
   • Repeat the process: count, subtract, and proceed.
5. Build the Output:
   • For each digit 0-9, append it to the result as many times as it occurs, in ascending order.

This approach ensures that each letter is only used once, and all digits are accounted for efficiently.

Example Walkthrough

Let's walk through the example input s = "owoztneoer":

1. Letter Counts:
   • o: 3, w: 1, z: 1, t: 1, n: 1, e: 2, r: 2
2. Unique Letters:
   • 'z': 1 → "zero" (0) occurs once.
   • 'w': 1 → "two" (2) occurs once.
   • Subtract letters for "zero": o-1, z-1, e-1, r-1
   • Subtract letters for "two": t-1, w-1, o-1
3. Updated Counts:
   • o: 1, w: 0, z: 0, t: 0, n: 1, e: 1, r: 1
4. Next Unique:
   • 'o': 1 → "one" (1) occurs once.
   • Subtract letters for "one": o-1, n-1, e-1
5. All counts zero. Digits found: 0, 1, 2. Result: "012"

Time and Space Complexity

Brute-force:

• Would involve generating all permutations of digit words and checking if their letters match s.
• Complexity: O(10^n) for n digits — infeasible for large inputs.

• Counting letters takes O(N), where N is the length of s.
• Processing digits and adjusting counts is O(1), since there are at most 10 digits.
• Space: O(1) for letter counts (since only 26 letters), O(1) for digit counts.
• Total: O(N) time and O(1) space.

Summary

The solution leverages the unique occurrence of certain letters in digit words to efficiently reconstruct the original digits. By counting letters and systematically removing identified digits, we avoid brute-force and achieve a linear-time solution. The approach is elegant because it uses the structure of the English language itself, turning what seems like a permutation problem into a simple counting and deduction exercise.

Code Implementation

from collections import Counter

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

        # Unique letters for each digit
        out[0] = count['z']
        out[2] = count['w']
        out[4] = count['u']
        out[6] = count['x']
        out[8] = count['g']

        # For non-unique, subtract those already counted
        out[1] = count['o'] - out[0] - out[2] - out[4]
        out[3] = count['h'] - out[8]
        out[5] = count['f'] - out[4]
        out[7] = count['s'] - out[6]
        out[9] = count['i'] - out[5] - out[6] - out[8]

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

#include <string>
#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    string originalDigits(string s) {
        vector<int> count(26, 0);
        for (char c : s) count[c - 'a']++;

        vector<int> out(10, 0);
        out[0] = count['z' - 'a'];
        out[2] = count['w' - 'a'];
        out[4] = count['u' - 'a'];
        out[6] = count['x' - 'a'];
        out[8] = count['g' - 'a'];

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

        string result;
        for (int i = 0; i <= 9; ++i) {
            result += string(out[i], '0' + i);
        }
        return result;
    }
};
      

class Solution {
    public String originalDigits(String s) {
        int[] count = new int[26];
        for (char c : s.toCharArray()) count[c - 'a']++;

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

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

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

var originalDigits = function(s) {
    const count = {};
    for (let c of s) count[c] = (count[c] || 0) + 1;

    const out = Array(10).fill(0);
    out[0] = count['z'] || 0;
    out[2] = count['w'] || 0;
    out[4] = count['u'] || 0;
    out[6] = count['x'] || 0;
    out[8] = count['g'] || 0;

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

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