Recover Sorted Digits from Scrambled English Number Words

A string contains a shuffled collection of letters from the English digit names zero, one, two, three, four, five, six, seven, eight, and nine. Recover the digits and return them in ascending order, preserving repetitions.

Implement recover_digits(letters: string) -> string.

Constraints & Assumptions

• Input has at most 100000 lowercase ASCII letters and is guaranteed to be a valid multiset of complete English digit names. The empty input represents no digits.
• Word boundaries and letter order have been lost. This is not substring segmentation of concatenated intact words.
• Output contains only 0 through 9, sorted nondecreasingly, with one digit per recovered word.
• Aim for O(input length + output length) time and constant-sized counting state, apart from output.

Examples

letters = "owoztneoer"
result = "012"

letters = "fviefuro"
result = "45"

The reported follow-up replaces English digit names with arbitrary customer-provided words for digits 0–9. Explain whether your reasoning still works, what would establish unique recoverability, and how you would detect or report ambiguous mappings. Do not assume arbitrary words contain a distinguishing letter. For example, assigning word a to one digit and word aa to another can make the same letter multiset represent different digit sequences.

Hint: Use structure specific to the fixed vocabulary

Some letters initially occur in only one digit name. After removing those words' contributions, other letters can become distinguishing.

Recover Sorted Digits from Shuffled English Names

Approach

Count the 26 letters, then eliminate digit words in the order 0,2,4,6,8,3,5,7,1,9. Their distinguishing letters in that order are z,w,u,x,g,h,f,s,o,i. Initially z,w,u,x,g occur only in their respective words. Removing their contributions makes h unique to three, f to five and s to seven; after those removals o identifies one, and i identifies nine. At every stage the remaining counts are exactly the letters from the unprocessed digit words, so the selected letter gives that digit multiplicity. Input validity guarantees nonnegative counts. Finally append digits from 0 through 9 with those multiplicities. Counting takes O(n), elimination uses fixed-size state and fixed vocabulary, and constructing k output digits costs O(k). For arbitrary customer words, this elimination requires a new proof and may fail. Model each word as its letter-count vector, form a matrix A, and seek nonnegative integer vectors x satisfying A*x=b. A particular input is uniquely recoverable exactly when it has one such solution; zero solutions means invalid, and multiple solutions mean ambiguous. Full column rank is sufficient for uniqueness, though not necessary for a particular input. An integer solver or bounded search can find one solution and then test for another, reporting ambiguity rather than guessing. Identical vectors or an a/aa pair demonstrate why arbitrary mappings need not be uniquely recoverable.

• Time complexity: O(n + k), where n is input length and k is output length
• Space complexity: O(1) counting state, excluding output