English To Maths

Easy
0/40
Average time to solve is 10m
7 upvotes

Problem statement

Ninja is trying to decipher a string 'S' that contains an out-of-order English representation of the digits 0 - 9.

Your task is to help Ninja to get back the digits in ascending order.

For example :

Given string ‘S’ = “toowen”, on the rearrangement of this string we get “onetwo” which implies “12”.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer 'T' representing the number of test cases.The 'T' test cases follow.

The first and the only line of each test case contains a single string 'S'.
Output Format : 
For each test case, print a string of digits 0-9 in ascending order which we can get after rearrangement of the given string 'S'.

The output for each test case is printed in a separate line.
Constraints : 
1 <= T <= 5
1 <= N <= 5000
‘S’ is always valid.

Where ‘N’ is the length of the string ‘S’.

Time limit: 1 sec

Note :

You do not need to print anything. It has already been taken care of. Just implement the given function.

Sample Input 1 :

2
ffoiuver
oenenniowt

Sample Output 1 :

45
129

Explanation Of Sample Output 1 :

Test Case 1: We can rearrange ‘S’ as “fourfive” which implies “45”.

Test Case 2 :  We can rearrange ‘S’ as “onetwonine” which implies “129”.

Sample Input 2 :

2
tsirxee
szixeoneor

Sample Output 2 :

36
016
Hint

Some alphabets are unique to some digits.

Approaches (2)
Brute force - 1

Here, we are going to use an observation that some alphabets are unique to some digits as illustrated below:

  • Zero: only digit with ‘Z’
  • Two: only digit with ‘W’
  • Four: only digit with ‘U’
  • Six: only digit with ‘X’
  • Eight: only digit with ‘G’

And as the string is always valid, to find the occurrence of other digits we need to find the frequency of any single character from the digit's English word.

 

To find “H” in three we just need to subtract the total “H” frequency with the frequency of “8” because both contain “H”.

Similarly, to find five we find the remaining “F” after four, to find seven we need to find “V” and for one and nine we need to calculate “O” and “I” respectively.

 

Algorithm:

  • Declare a map ‘FREQ’.
  • Traverse the string ‘S’ using ‘i’ ranges from 0 to S.length.
    • FREQ[S[i]]++
  • Declare an array ‘CNT’ of size 10 initialised with 0.
    • CNT[0] = FREQ[‘z’]
    • CNT[2] = FREQ[‘w’]
    • CNT[4] = FREQ[‘u’]
    • CNT[6] = FREQ[‘x’]
    • CNT[8] = FREQ[‘g’]
    • CNT[3] = FREQ[‘h’] - CNT[8]
    • CNT[5] = FREQ[‘f’] - CNT[4]
    • CNT[7] = FREQ[‘v’] - CNT[5]
    • CNT[1] = FREQ[‘o’] - CNT[0] - CNT[2] - CNT[4]
    • CNT[9] = FREQ[‘i’] - CNT[6] - CNT[5] - CNT[8]
  • Declare a string ‘RES’ = “”
  • For i in range (0, 10):
    • Repeat the steps till CNT[i] > 0.
    • CNT[i]--
    • RES += tostring(i)
  • Return ‘RES’.
Time Complexity

O(N), where ‘N’ is the length of the string ‘S’.

 

We are iterating all characters one by one and incrementing the frequency.

Space Complexity

O(1).

 

The total number of distinct characters is 26 (constant), and we are storing their frequencies, so, space complexity is O(1).

Code Solution
(100% EXP penalty)
English To Maths
Full screen
Console