Reconstruct Original Digits from English

Problem

Given a non-empty string containing an out-of-order English representation of digits 0-9, output the digits in ascending order.

Example 1:
Input: "owoztneoer"

Output: "012"

Example 2:
Input: "fviefuro"

Output: "45"

Note:

• Input contains only lowercase English letters.
• Input is guaranteed to be valid and can be transformed to its original digits. That means invalid inputs such as "abc" or "zerone" are not permitted.
• Input length is less than 50,000.

Solution

Store Digits in an Array Solution: O(n) time, O(n) space

public class Solution {
    public String originalDigits(String s) {
        //Same idea as mine, but this one use array of int! 
        int[] count = new int[10];
        for (int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            //digits with unique letter
            if (c == 'z') count[0]++;
            else if (c == 'w') count[2]++;
            else if (c == 'u') count[4]++; 
            else if (c == 'x') count[6]++;
            else if (c == 'g') count[8]++;
            //digits without any unique letters
            else if (c == 'o') count[1]++; //0, 2, 4
            else if (c == 'h') count[3]++; //8
            else if (c == 'f') count[5]++; //4
            else if (c == 's') count[7]++; //6
            else if (c == 'i') count[9]++; //5-6-8

        }
        count[1] -= (count[0] + count[2] + count[4]);
        count[3] -= count[8];
        count[5] -= count[4];
        count[7] -= count[6];
        count[9] -= (count[8] + count[5] + count[6]);

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i <= 9; i++)
            while(count[i]-- > 0) sb.append(i);
        return sb.toString();
    }
}

Analysis

The idea of this solution is to first get digits with unique letters
This means if some char appears, we are 100% sure it belongs to one digit (It happens to be all even numbers)
Then we check remaining digits without any unique letters
If they share common letters with unique digits, it would be better
Otherwise we need to pay attention on the sequence below the for statement
Ex. We must update count[5] before count[9], cause count[9] share letters with count[5]
At the end, we use StringBuilder to return numbers in increasing order