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

&nbsp;
Example 1:
Input: s = "owoztneoer"
Output: "012"
Example 2:
Input: s = "fviefuro"
Output: "45"

&nbsp;
Constraints:


	1 &lt;= s.length &lt;= 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.


class Solution:
    def originalDigits(self, s: str) -> str:
        c = dict()
        
        c[0] = s.count("z")
        c[2] = s.count("w")
        c[4] = s.count("u")
        c[6] = s.count("x")
        c[8] = s.count("g")
        
        c[3] = s.count("h") - c[8]
        c[5] = s.count("f") - c[4]
        c[7] = s.count("s") - c[6]
        
        c[9] = s.count("i") - (c[8] + c[5] + c[6])
        c[1] = s.count("o") - (c[0] + c[2] + c[4])
        
        c = sorted(c.items(), key = lambda x: x[0])
        ans = ""
        for k, v in c:
            ans += (str(k) * v)
        return ans
class Solution {

    // First letter is unique after previous entries have been handled:
    static final String[] UNIQUES = new String[] {
        "zero", "wto", "geiht", "xsi", "htree",
        "seven", "rfou", "one", "vfie", "inne"
    };

    // Values corresponding to order of uniqueness checks:
    static final int[] VALS = new int[] { 0, 2, 8, 6, 3, 7, 4, 1, 5, 9 };
    
	// Maps for checking uniqueness more conveniently:
    static final Map<Integer, List<Integer>> ORDERED_FREQ_MAP;
    static final Map<Integer, Integer> ORDERED_DIGIT_MAP;
    
    static {
	    // Initialize our ordered frequency map: 0-25 key to 0-25 values finishing the word:
        final LinkedHashMap<Integer, List<Integer>> orderedFreqMap = new LinkedHashMap<>();
		// Also initialize a digit lookup map, e.g. 'g' becomes 6 maps to 8 for ei[g]ht:
        final LinkedHashMap<Integer, Integer> orderedDigitMap = new LinkedHashMap<>();
        for (int i = 0; i < 10; ++i) {
            final char unique = UNIQUES[i].charAt(0);
            final int ui = convert(unique);
            orderedFreqMap.put(ui, converting(UNIQUES[i].substring(1).toCharArray()));
            orderedDigitMap.put(ui, VALS[i]);
        }
		// Let's make sure we aren't tempted to modify these since they're static.
        ORDERED_FREQ_MAP = Collections.unmodifiableMap(orderedFreqMap);
        ORDERED_DIGIT_MAP = Collections.unmodifiableMap(orderedDigitMap);
    }

    public String originalDigits(String s) {
	    // count frequencies of each letter in s:
        final int[] freqs = new int[26];
        for (int i = 0; i < s.length(); ++i) {
            freqs[convert(s.charAt(i))]++;
        }
		// Crate an array to store digit strings in order, e.g. '00000', '11, '2222222', etc.
        final String[] strings = new String[10];
		// Iterate through uniqueness checks in order:
        for (Map.Entry<Integer, List<Integer>> entry : ORDERED_FREQ_MAP.entrySet()) {
            final int index = entry.getKey(); // unique letter in 0-25 form
            final int value = ORDERED_DIGIT_MAP.get(index); // corresponding digit, e.g. 8 for 'g', 0 for 'z', etc.
            final int count = freqs[index]; // frequency of unique letter = frequency of corresponding digit
            if (count > 0) {
			    // update frequencies to remove the digit's word count times:
                freqs[index] -= count;
                for (int idx : entry.getValue()) {
                    freqs[idx] -= count;
                }
				// now create the digit string for the unique digit: the digit count times:
                strings[value] = String.valueOf(value).repeat(count);
            } else {
			    // count 0 - empty strring for this digit
                strings[value] = "";
            }
        }
		// append the digit strings in order
        final StringBuilder sb = new StringBuilder();
        for (String str : strings) {
            sb.append(str);
        }
		// and we are done!
        return sb.toString();
    }

    // Converts a character array into a list of 0-25 frequency values.
    private static final List<Integer> converting(char... carr) {
        final List<Integer> list = new ArrayList<>();
        for (char ch : carr) {
            list.add(convert(ch)); // converts each to 0-25
        }
        return Collections.unmodifiableList(list);
    }

    // Converts a-z to 0-26.  Bitwise AND with 31 gives a=1, z=26, so then subtract one.
    private static final Integer convert(char ch) {
        return (ch & 0x1f) - 1; // a->0, z->25
    }

}
class Solution {
public:
    
    vector<string> digits{"zero","one","two","three","four","five","six","seven","eight","nine"};
    void fun(int x,string &ans,vector<int> &m){
        for(int i = x;i<=9;i+=2){
            string t = digits[i];
            if(t.length() == 3){
                if(m[t[0]-'a'] > 0 && m[t[1]-'a'] > 0 && m[t[2]-'a'] > 0){
                    int min_o = min({m[t[0]-'a'] ,m[t[1]-'a'] , m[t[2]-'a']});
                    m[t[0]-'a'] -= min_o;
                    m[t[1]-'a'] -= min_o;
                    m[t[2]-'a'] -= min_o;
                    while(min_o--) ans += (char)(i +'0');
                }
            }else if(t.length() == 4){
                if(m[t[0]-'a'] > 0 && m[t[1]-'a'] > 0 && m[t[2]-'a'] > 0 && m[t[3]-'a'] > 0){
                    int min_o = min({m[t[0]-'a'] ,m[t[1]-'a'] , m[t[2]-'a'], m[t[3]-'a']});
                    m[t[0]-'a'] -= min_o;
                    m[t[1]-'a'] -= min_o;
                    m[t[2]-'a'] -= min_o;
                    m[t[3]-'a'] -= min_o;
                    while(min_o--) ans += (char)(i +'0');
                }
            }else if(t.length() == 5){
                if(m[t[0]-'a'] > 0 && m[t[1]-'a'] > 0 && m[t[2]-'a'] > 0 && m[t[3]-'a'] > 0 && m[t[4]-'a'] > 0){
                    int min_o = min({m[t[0]-'a'] ,m[t[1]-'a'] , m[t[2]-'a'], m[t[3]-'a'], m[t[4]-'a']});
                    m[t[0]-'a'] -= min_o;
                    m[t[1]-'a'] -= min_o;
                    m[t[2]-'a'] -= min_o;
                    m[t[3]-'a'] -= min_o;
                    m[t[4]-'a'] -= min_o;
                    while(min_o--) ans += (char)(i +'0');
                }
            }
        }
    }
    
    string originalDigits(string s) {
        string ans;
        vector<int> m(26,0);
        for(auto x:s) m[x-'a']++;
        fun(0,ans,m);
        fun(1,ans,m);
        sort(ans.begin(),ans.end());
        return ans;
    }
};
/**
 * @param {string} s
 * @return {string}
 */
 
var originalDigits = function(s) {
    const numberToWord = {
        0: 'zero',
        1: 'one',
        2: 'two',
        3: 'three',
        4: 'four',
        5: 'five',
        6: 'six',
        7: 'seven',
        8: 'eight',
        9: 'nine'
    }
    
    const letterToDigits = {}
    
    for(const key in numberToWord) {
        const currWord = numberToWord[key]
        
        for(const letter of currWord) {
            if(!(letter in letterToDigits)) letterToDigits[letter] = new Set()
            letterToDigits[letter].add(key)
        }
    }
    
    const inputFreqs = {}
    
    for(let i = 0; i < s.length; i++) {
        const currChar = s[i]
        
        if(!(currChar in inputFreqs)) inputFreqs[currChar] = 0
        inputFreqs[currChar]++
    }
    
    const letters = Object.keys(inputFreqs)
    
    const res = dfs(letters[0])
    
    return [...res].sort().join('')
    
    function dfs(currLetter) {
        if(!isValid(inputFreqs)) return null
        if(getTotalRemaining(inputFreqs) === 0) return []
        const possibleDigits = letterToDigits[currLetter]
        
        for(const digit of [...possibleDigits]) {
            const wordRepresentation = numberToWord[digit]
            
            subtract(wordRepresentation)
            
            if(!isValid(inputFreqs)) {
                addBack(wordRepresentation)
                continue
            }
            
            const nextLetter = getNext(inputFreqs)
            const nextDigits = dfs(nextLetter)
            
            if(nextDigits !== null) return [digit] + nextDigits
            
            addBack(wordRepresentation)
        }
        
        return null
    }
    
    function isValid(inputFreqs) {
        for(const key in inputFreqs) {
            const count = inputFreqs[key]
            
            if(count < 0) return false
        }
        
        return true
    }
    
    function getTotalRemaining(inputFreqs) {
        let sum = 0
        
        for(const key in inputFreqs) {
            const count = inputFreqs[key]
            
            sum += count
        }
        
        
        return sum
    }
    
    function subtract(word) {
        for(const char of word) {
            if(!(char in inputFreqs)) inputFreqs[char] = 0
            inputFreqs[char]--
        }
    }
    
    
    function addBack(word) {
        for(const char of word) {
            inputFreqs[char]++
        }
    }
    
    function getNext(inputFreqs) {
        for(const key in inputFreqs) {
            const count = inputFreqs[key]
            
            if(count > 0) return key
        }
        
        return null
    }
};
Reconstruct Original Digits from English