Problem

You are given a string formed by concatenating several words corresponding to the integers zero through nine and then anagramming.

For example, the input could be ’niesevehrtfeev’, which is an anagram of ’threefiveseven’. Note that there can be multiple instances of each integer.

Given this string, return the original integers in sorted order. In the example above, this would be 357.

Examples

Example 1

1
2
3

Input: "niesevehrtfeev"
Output: "357"
Explanation: The string is an anagram of "threefiveseven", which contains digits 3, 5, and 7 in sorted order.

Example 2

1
2
3

Input: "owtztnfur"
Output: "024"
Explanation: The string is an anagram of "zerotwofouru", which contains digits 0, 2, and 4 in sorted order.

Example 3

1
2
3

Input: "fviefuro"
Output: "45"
Explanation: The string is an anagram of "fourfive", which contains digits 4 and 5 in sorted order.

Example 4

1
2
3

Input: "nneonoene"
Output: "1199"
Explanation: The string is an anagram of "onenineonine", which contains digits 1, 9, 1, 9 in sorted order.

Solution

Method 1 - Character Frequency Analysis

Intuition

The key insight is that some digits have unique characters that only appear in their word representation. For example, ‘z’ only appears in “zero”, ‘w’ only in “two”, ‘u’ only in “four”, etc. We can use these unique characters to identify how many times each digit appears, then work our way through the remaining digits.

Approach

  1. Count character frequencies in the input string
  2. Identify digits with unique characters first:
    • ‘z’ → zero (0)
    • ‘w’ → two (2)
    • ‘u’ → four (4)
    • ‘x’ → six (6)
    • ‘g’ → eight (8)
  3. Remove counted characters from frequency map
  4. Identify remaining digits with semi-unique characters:
    • ‘f’ → five (5) (after removing four)
    • ’s’ → seven (7) (after removing six)
    • ‘h’ → three (3) (after removing eight)
  5. Handle remaining digits:
    • ‘i’ → nine (9) (after removing five, six, eight)
    • ‘o’ → one (1) (after removing zero, two, four)
  6. Build result string by repeating each digit according to its count

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution {
public:
    string originalDigits(string s) {
        vector<int> count(26, 0);
        for (char c : s) {
            count[c - 'a']++;
        }
        
        vector<int> nums(10, 0);
        
        // Digits with unique characters
        nums[0] = count['z' - 'a'];
        nums[2] = count['w' - 'a'];
        nums[4] = count['u' - 'a'];
        nums[6] = count['x' - 'a'];
        nums[8] = count['g' - 'a'];
        
        // Semi-unique after removing above
        nums[5] = count['f' - 'a'] - nums[4];
        nums[7] = count['s' - 'a'] - nums[6];
        nums[3] = count['h' - 'a'] - nums[8];
        
        // Remaining digits
        nums[9] = count['i' - 'a'] - nums[5] - nums[6] - nums[8];
        nums[1] = count['o' - 'a'] - nums[0] - nums[2] - nums[4];
        
        string ans = "";
        for (int i = 0; i < 10; i++) {
            ans += string(nums[i], '0' + i);
        }
        
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

func originalDigits(s string) string {
    count := make([]int, 26)
    for _, c := range s {
        count[c-'a']++
    }
    
    nums := make([]int, 10)
    
    // Digits with unique characters
    nums[0] = count['z'-'a']
    nums[2] = count['w'-'a']
    nums[4] = count['u'-'a']
    nums[6] = count['x'-'a']
    nums[8] = count['g'-'a']
    
    // Semi-unique after removing above
    nums[5] = count['f'-'a'] - nums[4]
    nums[7] = count['s'-'a'] - nums[6]
    nums[3] = count['h'-'a'] - nums[8]
    
    // Remaining digits
    nums[9] = count['i'-'a'] - nums[5] - nums[6] - nums[8]
    nums[1] = count['o'-'a'] - nums[0] - nums[2] - nums[4]
    
    var ans strings.Builder
    for i := 0; i < 10; i++ {
        for j := 0; j < nums[i]; j++ {
            ans.WriteByte(byte('0' + i))
        }
    }
    
    return ans.String()
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution {
    public String originalDigits(String s) {
        int[] count = new int[26];
        for (char c : s.toCharArray()) {
            count[c - 'a']++;
        }
        
        int[] nums = new int[10];
        
        // Digits with unique characters
        nums[0] = count['z' - 'a'];
        nums[2] = count['w' - 'a'];
        nums[4] = count['u' - 'a'];
        nums[6] = count['x' - 'a'];
        nums[8] = count['g' - 'a'];
        
        // Semi-unique after removing above
        nums[5] = count['f' - 'a'] - nums[4];
        nums[7] = count['s' - 'a'] - nums[6];
        nums[3] = count['h' - 'a'] - nums[8];
        
        // Remaining digits
        nums[9] = count['i' - 'a'] - nums[5] - nums[6] - nums[8];
        nums[1] = count['o' - 'a'] - nums[0] - nums[2] - nums[4];
        
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < nums[i]; j++) {
                ans.append((char)('0' + i));
            }
        }
        
        return ans.toString();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution:
    def originalDigits(self, s: str) -> str:
        count = [0] * 26
        for c in s:
            count[ord(c) - ord('a')] += 1
        
        nums = [0] * 10
        
        # Digits with unique characters
        nums[0] = count[ord('z') - ord('a')]
        nums[2] = count[ord('w') - ord('a')]
        nums[4] = count[ord('u') - ord('a')]
        nums[6] = count[ord('x') - ord('a')]
        nums[8] = count[ord('g') - ord('a')]
        
        # Semi-unique after removing above
        nums[5] = count[ord('f') - ord('a')] - nums[4]
        nums[7] = count[ord('s') - ord('a')] - nums[6]
        nums[3] = count[ord('h') - ord('a')] - nums[8]
        
        # Remaining digits
        nums[9] = count[ord('i') - ord('a')] - nums[5] - nums[6] - nums[8]
        nums[1] = count[ord('o') - ord('a')] - nums[0] - nums[2] - nums[4]
        
        ans = ""
        for i in range(10):
            ans += str(i) * nums[i]
        
        return ans

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the input string. We iterate through the string once to count characters, then perform constant time operations to determine digit counts.
  • 🧺 Space complexity: O(1), as we use fixed-size arrays for character counting and digit counting (size 26 and 10 respectively).

Method 2 - Direct Pattern Matching

Intuition

Another approach is to systematically subtract the character patterns of each digit word from our character count. We start with digits that have the most unique characteristics and work our way to the more ambiguous ones.

Approach

  1. Count all character frequencies in the input string
  2. Define digit patterns as character frequency maps for each digit word
  3. Process digits in strategic order to avoid conflicts:
    • First: digits with completely unique characters (0, 2, 4, 6, 8)
    • Second: digits with semi-unique characters (3, 5, 7)
    • Last: remaining digits (1, 9)
  4. For each digit, determine how many times it appears and subtract its pattern
  5. Build result by concatenating digits in sorted order

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution {
public:
    string originalDigits(string s) {
        vector<int> count(26, 0);
        for (char c : s) {
            count[c - 'a']++;
        }
        
        vector<string> words = {"zero", "one", "two", "three", "four", 
                               "five", "six", "seven", "eight", "nine"};
        vector<int> nums(10, 0);
        vector<int> order = {0, 2, 4, 6, 8, 3, 5, 7, 1, 9};
        
        for (int digit : order) {
            int cnt = INT_MAX;
            for (char c : words[digit]) {
                cnt = min(cnt, count[c - 'a']);
            }
            nums[digit] = cnt;
            
            // Subtract this digit's characters
            for (char c : words[digit]) {
                count[c - 'a'] -= cnt;
            }
        }
        
        string ans = "";
        for (int i = 0; i < 10; i++) {
            ans += string(nums[i], '0' + i);
        }
        
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

func originalDigits(s string) string {
    count := make([]int, 26)
    for _, c := range s {
        count[c-'a']++
    }
    
    words := []string{"zero", "one", "two", "three", "four", 
                     "five", "six", "seven", "eight", "nine"}
    nums := make([]int, 10)
    order := []int{0, 2, 4, 6, 8, 3, 5, 7, 1, 9}
    
    for _, digit := range order {
        cnt := 1000000
        for _, c := range words[digit] {
            if count[c-'a'] < cnt {
                cnt = count[c-'a']
            }
        }
        nums[digit] = cnt
        
        // Subtract this digit's characters
        for _, c := range words[digit] {
            count[c-'a'] -= cnt
        }
    }
    
    var ans strings.Builder
    for i := 0; i < 10; i++ {
        for j := 0; j < nums[i]; j++ {
            ans.WriteByte(byte('0' + i))
        }
    }
    
    return ans.String()
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution {
    public String originalDigits(String s) {
        int[] count = new int[26];
        for (char c : s.toCharArray()) {
            count[c - 'a']++;
        }
        
        String[] words = {"zero", "one", "two", "three", "four", 
                         "five", "six", "seven", "eight", "nine"};
        int[] nums = new int[10];
        int[] order = {0, 2, 4, 6, 8, 3, 5, 7, 1, 9};
        
        for (int digit : order) {
            int cnt = Integer.MAX_VALUE;
            for (char c : words[digit].toCharArray()) {
                cnt = Math.min(cnt, count[c - 'a']);
            }
            nums[digit] = cnt;
            
            // Subtract this digit's characters
            for (char c : words[digit].toCharArray()) {
                count[c - 'a'] -= cnt;
            }
        }
        
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < nums[i]; j++) {
                ans.append((char)('0' + i));
            }
        }
        
        return ans.toString();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution:
    def originalDigits(self, s: str) -> str:
        count = [0] * 26
        for c in s:
            count[ord(c) - ord('a')] += 1
        
        words = ["zero", "one", "two", "three", "four", 
                "five", "six", "seven", "eight", "nine"]
        nums = [0] * 10
        order = [0, 2, 4, 6, 8, 3, 5, 7, 1, 9]
        
        for digit in order:
            cnt = float('inf')
            for c in words[digit]:
                cnt = min(cnt, count[ord(c) - ord('a')])
            nums[digit] = cnt
            
            # Subtract this digit's characters
            for c in words[digit]:
                count[ord(c) - ord('a')] -= cnt
        
        ans = ""
        for i in range(10):
            ans += str(i) * nums[i]
        
        return ans

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the input string. We count characters once and then process each digit pattern in constant time.
  • 🧺 Space complexity: O(1), as we use constant space for character counting and digit word storage.