https://leetcode.com/problems/reconstruct-original-digits-from-english

Actually what is asked in this problem is to solve linear system of equations: imagine that we have f0, ... f9 frequencies of words zero, ... nine, then we need to solve 10 equations with 10 variables. We can look at this at slightly different angle:

  1. Let us look at word zero: we meet symbol z only in this word, so total number of times we have z in string is number of times we have word zero inside. So, what we do: we keep global counter cnt and subtract all frequencies, corresponding to letters z, e, r, o.
  2. Look at word two, we have symbol w only in this word, remove all words two.
  3. Look at word four, we have symbol u only in this word, remove all words four.
  4. Look at word six, we have symbol x only in this word, remove all words six.
  5. Look at word eight, we have symbol g only in this word, remove all words eight.
  6. Look at word one, we have symbol o only in this word if we look at words we still have, remove all words one.
  7. Look at word three, we have symbol t only in this word if we look at words we still have, remove all words three.
  8. Look at word five, we have symbol f only in this word if we look at words we still have, remove all words five.
  9. Look at word seven, we have symbol s only in this word if we look at words we still have, remove all words seven.
  10. Look at word nine, we have symbol n only in this word if we look at words we still have, remove all words nine.

Complexity: time complexity is just O(n), where n is length of s, because first we create counter and then we iterate over 10 digits and update cnt in O(1) time. Space complexity is O(n) as well to format our answer.

class Solution:
    def originalDigits(self, s):
        cnt = Counter(s)
        Digits = ["zero","two","four","six","eight","one","three","five","seven","nine"]
        Corresp = [0,2,4,6,8,1,3,5,7,9]
        Counters = [Counter(digit) for digit in Digits]
        Found = [0]*10
        for it, C in enumerate(Counters):
            k = min(cnt[x]//C[x] for x in C)
            for i in C.keys(): C[i] *= k
            cnt -= C
            Found[Corresp[it]] = k
            
        return "".join([str(i)*Found[i] for i in range(10)])

If you have any question, feel free to ask. If you like the explanations, please Upvote!

If you like the solution, you can upvote it on leetcode discussion section: Problem 0423