423. Reconstruct Original Digits from English
Problem Description
The problem presents us with a string s
that comprises jumbled letters representing English words for digits zero to nine. For example, the word for zero "zero" includes the letters "z", "e", "r", and "o". Our task is to rearrange these jumbled letters to figure out what digits they represent and then return those digits sorted in ascending order. As an example, if the input string is "owoztneoer", the output should be "012" corresponding to the digits one, zero, and two represented by the words "one", "zero", and "two" that can be formed from the given letters.
Intuition
The solution approach is based on the observation that certain letters uniquely identify some numbers. For instance, the letter "z" only appears in "zero", and the letter "w" only shows up in "two". We can use these unique letters to immediately find how many times a particular digit occurs in the string.
The Python code implements this approach by creating a counter cnt
of ten elements representing the digits 0 to 9. Then we fill in this counter based on the frequency of the unique identifiers:
z
appears only in "zero", socnt[0]
is set to the count of 'z'.w
appears only in "two", socnt[2]
is set to the count of 'w'.u
appears only in "four", socnt[4]
is set to the count of 'u'.x
appears only in "six", socnt[6]
is set to the count of 'x'.g
appears only in "eight", socnt[8]
is set to the count of 'g'.
After identifying and counting the digits with unique letters, the code then uses this information to determine the counts of other digits, which have letters that can be shared with the digits already counted. This is performed through subtraction:
h
appears in "three" and "eight", but since we've already counted the 'h' from "eight",cnt[3]
can be calculated by subtractingcnt[8]
from the count of 'h'.f
appears in "five" and "four", butcnt[4]
is already known, so subtract that from the count of 'f' to findcnt[5]
.s
appears in "seven" and "six", subtractcnt[6]
from the count of 's' to getcnt[7]
.- For
cnt[1]
, it requires the count of the letter 'o', which appears in "zero", "one", "two", and "four". We've already found the counts for "zero", "two", and "four", so we subtract those from the count of 'o'. - The digit 'nine' is represented by 'i', which appears in "five", "six", "eight", and "nine". Again, subtract the counts of "five", "six", and "eight", that have already been accounted for, from the count of 'i', to arrive at
cnt[9]
.
Finally, the code concatenates the digits together into a string, with each digit repeated as many times as it was counted, and returns this string as the result.
Learn more about Math patterns.
Solution Approach
The solution utilizes several powerful concepts in Python, such as the Counter
class from the collections
module for frequency counting and list comprehension for building the final output.
Here's a step-by-step walkthrough:
-
First, the program imports the
Counter
class from thecollections
module, which is used to count the frequency of each character in the input strings
. -
counter = Counter(s)
: This line creates an instance of theCounter
object that contains the frequency of each character in the string. -
The
cnt
list of length 10 is initialized to store the count of each digit from 0 to 9. Initially, all values incnt
are set to 0. -
The code then identifies the counts of digits with unique characters:
cnt[0]
is set to the count of'z'
, which only appears in "zero".cnt[2]
is set to the count of'w'
, which only appears in "two".- And so on for
cnt[4]
,cnt[6]
, andcnt[8]
.
-
With those unique digit counts determined, the counts for the other digits that share characters can now be calculated:
cnt[3]
is the count of'h'
(from "three" and "eight") minuscnt[8]
.cnt[5]
is the count of'f'
(from "five" and "four") minuscnt[4]
.cnt[7]
is the count of's'
(from "seven" and "six") minuscnt[6]
.cnt[1]
is the count of'o'
(from "zero", "one", "two", "four") minus the counts ofcnt[0]
,cnt[2]
, andcnt[4]
.cnt[9]
is the count of'i'
(from "five", "six", "eight", "nine") minuscnt[5]
,cnt[6]
, andcnt[8]
.
-
Finally, once all the counts are determined, the code uses list comprehension to construct the output string. This is done with
''.join(cnt[i] * str(i) for i in range(10))
, which iterates over the digits 0 through 9, repeating each digit a number of times equal to its count, and then joining them together into one string.
This code is a clever exploit of the uniqueness of certain characters in the English language spelling of these digit words and the smart use of character frequency counting to compute the overall digit counts indirectly.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach using a small example. Suppose our input string is s = "nnei"
which we need to organize into sorted digits.
- We start by using the Counter class to determine the frequency of each character:
1from collections import Counter 2counter = Counter(s) # s = 'nnei'
After this step, counter
looks like this: Counter({'n': 2, 'e': 1, 'i': 1})
.
- We initialize an array
cnt
with 10 zeroes to hold the counts for each digit:
1cnt = [0] * 10
-
Next, we can deduce the unique counts for some digits; however, in our example
s = "nnei"
, there are no unique digit identifiers like "z" for zero, "w" for two, "u" for four, "x" for six, or "g" for eight. Thus, values incnt
remain unaltered for these particular digits. -
From the remaining characters, we infer the following:
- The letter 'n' appears twice, and since it can only be part of "nine" or "one", we don't have enough information to determine the count directly.
- The letter 'e' appears once, which is shared by "one", "three", "five", "seven", and "nine".
- The letter 'i' appears once; it can be from "five", "six", "eight", or "nine".
-
Based on our Counter, we can take an educated guess. The only digit that can be formed is "nine", which uses all the letters in our counter: 'n', 'i', 'n', 'e'. Therefore, we set
cnt[9]
to 1:
1cnt[9] = counter['i'] # counter['i'] is 1 for 'nine'
After this, it'll also be clear that since we have identified 'nine' and have used up all 'n', 'e' and 'i' from the string, cnt[1]
, cnt[3]
, cnt[5]
, and cnt[7]
will not be incremented as there are no remaining counts of 'n', 'e', or 'i'.
- Following these deductions, we can now construct our result. Since only 'nine' can be formed, our result string will only contain '9':
1result = ''.join(str(i) * cnt[i] for i in range(10)) # generates '9'
After these steps, the output string is '9', which is the expected result for the input string s = "nnei"
.
Solution Implementation
1from collections import Counter
2
3class Solution:
4 def original_digits(self, s: str) -> str:
5 # Create a counter object to count occurrences of each character in the string
6 char_count = Counter(s)
7 # Initialize a list to store the count of each digit from 0 to 9
8 digit_count = [0] * 10
9
10 # Each unique character can identify a number:
11 # 'z' is present only in "zero" \
12 digit_count[0] = char_count['z']
13 # 'w' is present only in "two"
14 digit_count[2] = char_count['w']
15 # 'u' is present only in "four"
16 digit_count[4] = char_count['u']
17 # 'x' is present only in "six"
18 digit_count[6] = char_count['x']
19 # 'g' is present only in "eight"
20 digit_count[8] = char_count['g']
21
22 # Now we proceed to find the count of the other numbers
23 # 'h' is present in "three" and "eight", but we have already counted "eight" occurrences
24 digit_count[3] = char_count['h'] - digit_count[8]
25 # 'f' is present in "five" and "four", but we have already counted "four" occurrences
26 digit_count[5] = char_count['f'] - digit_count[4]
27 # 's' is present in "seven" and "six", but we have already counted "six" occurrences
28 digit_count[7] = char_count['s'] - digit_count[6]
29
30 # For ones, it is present in "one", "zero", "two", and "four", which are already counted
31 digit_count[1] = char_count['o'] - digit_count[0] - digit_count[2] - digit_count[4]
32 # 'i' is present in "nine", "five", "six", and "eight", which are already counted
33 digit_count[9] = char_count['i'] - digit_count[5] - digit_count[6] - digit_count[8]
34
35 # Construct the final string with the counted digits
36 result = ''.join(str(i) * digit_count[i] for i in range(10))
37 return result
38
1class Solution {
2 public String originalDigits(String s) {
3 // Create an array to keep count of all alphabet characters within the string
4 int[] charCounter = new int[26];
5 // Count the frequency of each character in the string
6 for (char c : s.toCharArray()) {
7 charCounter[c - 'a']++;
8 }
9
10 // Create an array to count the occurrences of each digit (0-9) in the string
11 int[] digitCounts = new int[10];
12
13 // Count unique letters that only appear in a single number's spelling.
14 // This gives us a definitive count of certain digits.
15 digitCounts[0] = charCounter['z' - 'a']; // Zero
16 digitCounts[2] = charCounter['w' - 'a']; // Two
17 digitCounts[4] = charCounter['u' - 'a']; // Four
18 digitCounts[6] = charCounter['x' - 'a']; // Six
19 digitCounts[8] = charCounter['g' - 'a']; // Eight
20
21 // For other numbers which share letters, we subtract the counts of
22 // already identified unique ones to get the correct digit counts.
23 digitCounts[3] = charCounter['h' - 'a'] - digitCounts[8]; // Three (h is also in eight)
24 digitCounts[5] = charCounter['f' - 'a'] - digitCounts[4]; // Five (f is also in four)
25 digitCounts[7] = charCounter['s' - 'a'] - digitCounts[6]; // Seven (s is also in six)
26
27 // For one and nine, we deduce their counts by subtracting the counts of digits
28 // that share the same letters and have been previously determined.
29 digitCounts[1] = charCounter['o' - 'a'] - digitCounts[0] - digitCounts[2] - digitCounts[4]; // One
30 digitCounts[9] = charCounter['i' - 'a'] - digitCounts[5] - digitCounts[6] - digitCounts[8]; // Nine
31
32 // Construct the final digits string in ascending order.
33 StringBuilder result = new StringBuilder();
34 for (int i = 0; i < 10; ++i) {
35 for (int j = 0; j < digitCounts[i]; ++j) {
36 result.append(i);
37 }
38 }
39
40 // Return the constructed string which represents the original digits in ascending order.
41 return result.toString();
42 }
43}
44
1#include <vector>
2#include <string>
3
4class Solution {
5public:
6 string originalDigits(string s) {
7 // Creating a frequency counter for each alphabet letter
8 vector<int> alphaCounter(26, 0);
9 for (char c : s) {
10 ++alphaCounter[c - 'a'];
11 }
12
13 // Creating a frequency counter for digits 0 through 9
14 vector<int> digitCounter(10, 0);
15
16 // Counting occurrences of letters that uniquely identify a digit
17 digitCounter[0] = alphaCounter['z' - 'a']; // The presence of 'z' indicates 'zero'
18 digitCounter[2] = alphaCounter['w' - 'a']; // The presence of 'w' indicates 'two'
19 digitCounter[4] = alphaCounter['u' - 'a']; // The presence of 'u' indicates 'four'
20 digitCounter[6] = alphaCounter['x' - 'a']; // The presence of 'x' indicates 'six'
21 digitCounter[8] = alphaCounter['g' - 'a']; // The presence of 'g' indicates 'eight'
22
23 // Subtracting counts of digits where letters are shared with the unique-letters digits
24 digitCounter[3] = alphaCounter['h' - 'a'] - digitCounter[8]; // 'three' is indicated by 'h', but 'eight' also contains 'h'
25 digitCounter[5] = alphaCounter['f' - 'a'] - digitCounter[4]; // 'five' is indicated by 'f', but 'four' also contains 'f'
26 digitCounter[7] = alphaCounter['s' - 'a'] - digitCounter[6]; // 'seven' is indicated by 's', but 'six' also contains 's'
27
28 // For digits 'one' and 'nine', which share letters with multiple digits
29 digitCounter[1] = alphaCounter['o' - 'a'] - digitCounter[0] - digitCounter[2] - digitCounter[4];
30 digitCounter[9] = alphaCounter['i' - 'a'] - digitCounter[5] - digitCounter[6] - digitCounter[8];
31
32 // Constructing the output string based on the digits' frequency
33 string result;
34 for (int i = 0; i < 10; ++i) {
35 for (int j = 0; j < digitCounter[i]; ++j) {
36 result += char(i + '0'); // Append the numeric digit i, converted to a character
37 }
38 }
39
40 return result;
41 }
42};
43
1// Define function to get the original digits from the input string.
2function originalDigits(s: string): string {
3 // Create a frequency counter for each alphabet letter
4 const alphaCounter: number[] = new Array(26).fill(0);
5 for (const char of s) {
6 alphaCounter[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
7 }
8
9 // Create a frequency counter for digits 0 through 9
10 const digitCounter: number[] = new Array(10).fill(0);
11
12 // Count occurrences of letters that uniquely identify a digit
13 digitCounter[0] = alphaCounter['z'.charCodeAt(0) - 'a'.charCodeAt(0)]; // 0 is signified by 'z'
14 digitCounter[2] = alphaCounter['w'.charCodeAt(0) - 'a'.charCodeAt(0)]; // 2 is signified by 'w'
15 digitCounter[4] = alphaCounter['u'.charCodeAt(0) - 'a'.charCodeAt(0)]; // 4 is signified by 'u'
16 digitCounter[6] = alphaCounter['x'.charCodeAt(0) - 'a'.charCodeAt(0)]; // 6 is signified by 'x'
17 digitCounter[8] = alphaCounter['g'.charCodeAt(0) - 'a'.charCodeAt(0)]; // 8 is signified by 'g'
18
19 // Deduct counts of letters from previous findings to find the rest of the digits
20 digitCounter[3] = alphaCounter['h'.charCodeAt(0) - 'a'.charCodeAt(0)] - digitCounter[8]; // 3 contains 'h', adjusted for '8'
21 digitCounter[5] = alphaCounter['f'.charCodeAt(0) - 'a'.charCodeAt(0)] - digitCounter[4]; // 5 contains 'f', adjusted for '4'
22 digitCounter[7] = alphaCounter['s'.charCodeAt(0) - 'a'.charCodeAt(0)] - digitCounter[6]; // 7 contains 's', adjusted for '6'
23
24 // Special cases for 'one' and 'nine'
25 digitCounter[1] = alphaCounter['o'.charCodeAt(0) - 'a'.charCodeAt(0)] - digitCounter[0] - digitCounter[2] - digitCounter[4]; // '1' contains 'o'
26 digitCounter[9] = alphaCounter['i'.charCodeAt(0) - 'a'.charCodeAt(0)] - digitCounter[5] - digitCounter[6] - digitCounter[8]; // '9' contains 'i'
27
28 // Construct the output string based on the digits' frequency
29 let result: string = '';
30 for (let i = 0; i < 10; ++i) {
31 for (let j = 0; j < digitCounter[i]; ++j) {
32 result += i.toString(); // Append the actual numeric digit i
33 }
34 }
35
36 return result;
37}
38
39// Example of how to use the function
40const inputString = "owoztneoer";
41const outputDigits = originalDigits(inputString);
42console.log(outputDigits); // Should print the sorted original digits found in the string
43
Time and Space Complexity
The given Python code uses a Counter
to track the frequency of characters in the string s
, and then deduces the counts for each digit from 0 to 9. The final string is composed based on these counts.
Time Complexity:
- Constructing the
Counter
takesO(n)
time, wheren
is the length of the strings
. - The code includes ten direct assignments (for
cnt[0]
tocnt[8]
) and three subtraction operations (forcnt[9]
,cnt[7]
, andcnt[5]
) which all happen in constant time, i.e.,O(1)
each. - The last operation consists of iterating over the range 0 to 9 and concatenating the digits the number of times they appear. This is
O(m)
wherem
denotes the total number of digits in the output. Note thatm
depends on the inputs
and its distribution of characters representing digits.
Adding all these operations together, we arrive at a final time complexity of O(n + m)
. In the worst case, the output string m
could be proportional to the input string n
, which means m
could be as big as O(n)
. Therefore, the overall time complexity simplifies to O(n)
.
Space Complexity:
- The
Counter
which stores the frequency of each character needs space up toO(k)
, wherek
is the number of unique characters in strings
. Since we are dealing with English letters and a few additional characters,k
is bounded by a constant (at most 26 for letters plus additional characters for digits), so we can consider itO(1)
. - The
cnt
array uses constant space because it is of a fixed size of 10, which meansO(1)
. - The output string does not use extra space that grows with input
s
, as it's just a representation ofcnt
.
This leads to a space complexity of O(1)
since both the Counter
and the cnt
array occupy constant space.
Thus, the given code has a time complexity of O(n)
and a space complexity of O(1)
.
Learn more about how to find time and space complexity quickly using problem constraints.
In a binary min heap, the maximum element can be found in:
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.