Reconstruct Original Digits from English — Editorial

Opening the reading…

Intuitionwhy unique letters turn an unordered jumble into counts

The input is a collection of complete digit words with their letters shuffled together. Order is therefore irrelevant; the useful information is how many times each letter appears. If a letter belongs to only one digit word, its frequency directly tells you how many copies of that digit are present.

Five letters have this property immediately: z identifies zero, w identifies two, u identifies four, x identifies six, and g identifies eight. Once you know those counts, subtract every letter contributed by those words. The remaining frequencies then expose one unique letter for each remaining digit: o for one, t for three, f for five, s for seven, and i for nine. Finally, emit each digit as many times as its count, from 0 through 9.

Approachcount, remove, identify, and rebuild

Count the occurrences of every character in s using an array indexed by c - 'a', because the input order carries no information and only frequencies can distinguish the hidden words.

Set the counts of digits 0, 2, 4, 6, and 8 from z, w, u, x, and g respectively, because each of those letters occurs in exactly one digit word.

Subtract the letters of every identified word from the frequency array, using its full digit count rather than subtracting just once; otherwise letters belonging to repeated copies remain and falsely suggest more digits.

Set the counts of digits 1, 3, 5, 7, and 9 from o, t, f, s, and i respectively, because removing the first five digit groups makes each of these letters unique among the remaining words.

Create the answer by visiting digits from 0 through 9 and appending each digit exactly as many times as its recorded count, because the required result is sorted numerically rather than arranged in discovery order.

Complexitythe alphabet and digit vocabulary are fixed

MEASURE	BOUND	WHY
Time	O(n)	Building the frequency array reads each input character once. The later scans touch only the fixed ten digit words and append exactly n output characters, so their total work is linear in the input size.
Space	O(1) extra	The frequency array, digit counts, and ten fixed word descriptions use constant space. The returned string contains n characters but is required output and is excluded from the extra-space bound; the bound stays O(1) even for the worst input size.

Here n is the length of s. The alphabet has 26 letters and there are 10 digit words, both fixed constants.

Annotated solutionC++ · frequency counting with staged subtraction

CPPCount letters, remove the five uniquely identified digit groups, then emit all digits in ascending order.

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

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

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

        string digits[] = {"zero", "two", "four", "six", "eight"};
        int nums[] = {0, 2, 4, 6, 8};

        for (int i = 0; i < 5; i++) {
            for (char c : digits[i]) {
                cnt[c - 'a'] -= out[nums[i]];
            }
        }

        out[1] = cnt['o' - 'a'];
        out[3] = cnt['t' - 'a'];
        out[5] = cnt['f' - 'a'];
        out[7] = cnt['s' - 'a'];
        out[9] = cnt['i' - 'a'];

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

The subtraction loop is the bridge between the two groups of digits. For example, every discovered zero consumes one z, one e, one r, and one o from the frequency array. After all five unique-letter digits are removed, the remaining count of o cannot come from zero, two, four, six, or eight, so it is exactly the number of ones. The same reasoning applies to the other four residual letters.