1
/**
2
 * @param {string} s
3
 * @return {string}
4
 */
5

6
var originalDigits = function (s) {
7
  const numberToWord = {
8
    0: "zero",
9
    1: "one",
10
    2: "two",
11
    3: "three",
12
    4: "four",
13
    5: "five",
14
    6: "six",
15
    7: "seven",
16
    8: "eight",
17
    9: "nine",
18
  };
19

20
  const letterToDigits = {};
21

22
  for (const key in numberToWord) {
23
    const currWord = numberToWord[key];
24

25
    for (const letter of currWord) {
26
      if (!(letter in letterToDigits)) letterToDigits[letter] = new Set();
27
      letterToDigits[letter].add(key);
28
    }
29
  }
30

31
  const inputFreqs = {};
32

33
  for (let i = 0; i < s.length; i++) {
34
    const currChar = s[i];
35

36
    if (!(currChar in inputFreqs)) inputFreqs[currChar] = 0;
37
    inputFreqs[currChar]++;
38
  }
39

40
  const letters = Object.keys(inputFreqs);
41

42
  const res = dfs(letters[0]);
43

44
  return [...res].sort().join("");
45

46
  function dfs(currLetter) {
47
    if (!isValid(inputFreqs)) return null;
48
    if (getTotalRemaining(inputFreqs) === 0) return [];
49
    const possibleDigits = letterToDigits[currLetter];
50

51
    for (const digit of [...possibleDigits]) {
52
      const wordRepresentation = numberToWord[digit];
53

54
      subtract(wordRepresentation);
55

56
      if (!isValid(inputFreqs)) {
57
        addBack(wordRepresentation);
58
        continue;
59
      }
60

61
      const nextLetter = getNext(inputFreqs);
62
      const nextDigits = dfs(nextLetter);
63

64
      if (nextDigits !== null) return [digit] + nextDigits;
65

66
      addBack(wordRepresentation);
67
    }
68

69
    return null;
70
  }
71

72
  function isValid(inputFreqs) {
73
    for (const key in inputFreqs) {
74
      const count = inputFreqs[key];
75

76
      if (count < 0) return false;
77
    }
78

79
    return true;
80
  }
81

82
  function getTotalRemaining(inputFreqs) {
83
    let sum = 0;
84

85
    for (const key in inputFreqs) {
86
      const count = inputFreqs[key];
87

88
      sum += count;
89
    }
90

91
    return sum;
92
  }
93

94
  function subtract(word) {
95
    for (const char of word) {
96
      if (!(char in inputFreqs)) inputFreqs[char] = 0;
97
      inputFreqs[char]--;
98
    }
99
  }
100

101
  function addBack(word) {
102
    for (const char of word) {
103
      inputFreqs[char]++;
104
    }
105
  }
106

107
  function getNext(inputFreqs) {
108
    for (const key in inputFreqs) {
109
      const count = inputFreqs[key];
110

111
      if (count > 0) return key;
112
    }
113

114
    return null;
115
  }
116
};