Reconstruct Original Digits from English

Problem Statement

In this task, we are given a string s which includes a jumbled representation of English words corresponding to digits from 0 to 9. Our goal is to identify the digits represented in the string and then return these digits sorted in ascending order. Each character in the string contributes to the composition of one or more digit names. The complexity lies in deciphering the correct composition of digits based on potentially overlapping representations.

Examples

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.

Approach and Intuition

In approaching this problem, the intuition revolves around recognizing unique characters or combinations that can identify each numeral from 0 to 9. Considering the constraints and the way English represents numerical digits, certain characters are key in distinguishing one numeral from another.

1. Count Occurrences:

   • Begin by counting the occurrences of every character in the string. Since each English word representation of a number is fixed, the frequency of each character should help in deducing the presence of specific numbers.

2. Identify Unique Markers:

   • Some numbers can be directly identified by unique characters which are not shared by the representation of other numbers. For example, 'z' only appears in "zero," 'w' only appears in "two," 'u' only in "four," 'x' in "six," and 'g' in "eight".

3. Handle Overlapping Characters:

   • Once the numbers with unique identifiers have been accounted for, the next step involves dealing with numbers whose characters may overlap with others. For instance, both "one" and "nine" contain the character 'n'. However, the counts already used for numbers identified in the previous step can assist in resolving these ambiguities.

4. Construct the Result:

   • Using the counts of identified numbers, construct the resultant string of digits in ascending order. Given the nature of the problem (each character contributing to the formation of a legitimate number representation in English), the validity of the input ensures that this approach will always yield the correct sequence of digits.

5. Edge Cases:

   • Given the constraints, including the minimum and maximum possible lengths of the string, and the fixed set of characters, the procedure should effectively handle any input obeying the specified rules. Always ensure after performing deductions based on unique and overlapping characters that the counts used do not exceed the actual occurrences in the initial character count.

By following these steps systematically, one can unravel the jumbled English representations into a clear sequence of digits sorted numerically.

Solutions

class Solution {
  public String findDigitsInString(String input) {
    char[] frequency = new char[26 + (int)'a'];
    for(char charact : input.toCharArray()) {
      frequency[charact]++;
    }

    int[] digitCounts = new int[10];
    digitCounts[0] = frequency['z'];
    digitCounts[2] = frequency['w'];
    digitCounts[4] = frequency['u'];
    digitCounts[6] = frequency['x'];
    digitCounts[8] = frequency['g'];
    digitCounts[3] = frequency['h'] - digitCounts[8];
    digitCounts[5] = frequency['f'] - digitCounts[4];
    digitCounts[7] = frequency['s'] - digitCounts[6];
    digitCounts[9] = frequency['i'] - digitCounts[5] - digitCounts[6] - digitCounts[8];
    digitCounts[1] = frequency['n'] - digitCounts[7] - 2 * digitCounts[9];

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