Reconstruct Original Digits from English

medium string math hash map

Problem

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

Inputs = "owoztneoer"

Output"012"

"zero" has unique 'z', "two" has unique 'w', "one" has unique 'o' after removing zero/two/four.

s (digit words scrambled)

def original_digits(s):
    from collections import Counter
    c = Counter(s)
    n = [0] * 10
    n[0] = c['z']; n[2] = c['w']; n[4] = c['u']
    n[6] = c['x']; n[8] = c['g']
    n[3] = c['h'] - n[8]
    n[5] = c['f'] - n[4]
    n[7] = c['s'] - n[6]
    n[1] = c['o'] - n[0] - n[2] - n[4]
    n[9] = c['i'] - n[5] - n[6] - n[8]
    return "".join(str(d) * n[d] for d in range(10))

function originalDigits(s) {
  const c = {};
  for (const ch of s) c[ch] = (c[ch] || 0) + 1;
  const g = ch => c[ch] || 0;
  const n = new Array(10).fill(0);
  n[0] = g('z'); n[2] = g('w'); n[4] = g('u');
  n[6] = g('x'); n[8] = g('g');
  n[3] = g('h') - n[8];
  n[5] = g('f') - n[4];
  n[7] = g('s') - n[6];
  n[1] = g('o') - n[0] - n[2] - n[4];
  n[9] = g('i') - n[5] - n[6] - n[8];
  let out = "";
  for (let d = 0; d < 10; d++) out += String(d).repeat(n[d]);
  return out;
}

class Solution {
    public String originalDigits(String s) {
        int[] c = new int[26];
        for (char ch : s.toCharArray()) c[ch - 'a']++;
        int[] n = new int[10];
        n[0] = c['z' - 'a']; n[2] = c['w' - 'a']; n[4] = c['u' - 'a'];
        n[6] = c['x' - 'a']; n[8] = c['g' - 'a'];
        n[3] = c['h' - 'a'] - n[8];
        n[5] = c['f' - 'a'] - n[4];
        n[7] = c['s' - 'a'] - n[6];
        n[1] = c['o' - 'a'] - n[0] - n[2] - n[4];
        n[9] = c['i' - 'a'] - n[5] - n[6] - n[8];
        StringBuilder sb = new StringBuilder();
        for (int d = 0; d < 10; d++) for (int k = 0; k < n[d]; k++) sb.append(d);
        return sb.toString();
    }
}

string originalDigits(string s) {
    int c[26] = {0};
    for (char ch : s) c[ch - 'a']++;
    int n[10] = {0};
    n[0] = c['z' - 'a']; n[2] = c['w' - 'a']; n[4] = c['u' - 'a'];
    n[6] = c['x' - 'a']; n[8] = c['g' - 'a'];
    n[3] = c['h' - 'a'] - n[8];
    n[5] = c['f' - 'a'] - n[4];
    n[7] = c['s' - 'a'] - n[6];
    n[1] = c['o' - 'a'] - n[0] - n[2] - n[4];
    n[9] = c['i' - 'a'] - n[5] - n[6] - n[8];
    string out;
    for (int d = 0; d < 10; d++) for (int k = 0; k < n[d]; k++) out += ('0' + d);
    return out;
}

Explanation

The letters are scrambled, but some digit words contain a letter that no other word does. For example only "zero" has a z, only "two" has a w, only "four" has a u, only "six" has an x, and only "eight" has a g. Counting those letters directly gives us the counts of 0, 2, 4, 6, and 8.

Once those are known, other digits become unique too. The letter h appears in "three" and "eight", and we already know how many eights there are, so n[3] = count('h') - n[8]. The same subtraction trick gives 5 (from f, minus the fours), 7 (from s, minus the sixes), 1 (from o, minus zero/two/four), and 9 (from i, minus five/six/eight).

So we first count every letter in s, then fill the array n[0..9] in that careful order so each step only depends on counts already solved.

Finally we build the answer in ascending order by repeating each digit d exactly n[d] times and joining them.

Example: s = "owoztneoer". We find one z (→ 0), one w (→ 2), and after removing those the leftover o gives one 1. Sorted, that is "012".

Time: O(n) Space: O(1)