<p>Given a string <code>s</code> containing an out-of-order English representation of digits <code>0-9</code>, return <em>the digits in <strong>ascending</strong> order</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> s = "owoztneoer"
<strong>Output:</strong> "012"
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> s = "fviefuro"
<strong>Output:</strong> "45"
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>
	<li><code>s[i]</code> is one of the characters <code>[&quot;e&quot;,&quot;g&quot;,&quot;f&quot;,&quot;i&quot;,&quot;h&quot;,&quot;o&quot;,&quot;n&quot;,&quot;s&quot;,&quot;r&quot;,&quot;u&quot;,&quot;t&quot;,&quot;w&quot;,&quot;v&quot;,&quot;x&quot;,&quot;z&quot;]</code>.</li>
	<li><code>s</code> is <strong>guaranteed</strong> to be valid.</li>
</ul>

class Solution 
{
private:
    struct WordDigitPair
    {
        std::string_view word;
        int digit = 0;
    };

    // Sorted in order of unique letters and length
    const std::vector<WordDigitPair> s_wordDigitPairs = 
    {
        {"zero", 0},
        {"two", 2},
        {"six", 6},
        {"eight", 8},
        {"seven", 7},
        {"three", 3},
        {"four", 4},
        {"five", 5},
        {"nine", 9},
        {"one", 1},
    };

public:
    string originalDigits(string& input)
    {
        std::map<char, int> mapCharCount;
        for(char c: input)
        {
            mapCharCount[c] += 1;
        }

        // Get the digits from the string
        std::vector<int> digits;
        for(const auto& wordDigitPair: s_wordDigitPairs)
        {
            int minCharsCount = std::numeric_limits<int>::max();
            for(char c: wordDigitPair.word)
            {
                minCharsCount = std::min(mapCharCount[c], minCharsCount);
            }
            for(char c: wordDigitPair.word)
            {
                mapCharCount[c] -= minCharsCount;
            }
            for(int i = 0; i < minCharsCount; ++i)
            {
                digits.push_back(wordDigitPair.digit);
            }
        }

        std::sort(digits.begin(), digits.end());

        std::string output;
        for(int digit: digits)
        {
            char digitChar = '0' + digit;
            output += digitChar;
        }    
        return output;
    }
};
13100