Problem of the day
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”.
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.
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.
2
ffoiuver
oenenniowt
45
129
Test Case 1: We can rearrange ‘S’ as “fourfive” which implies “45”.
Test Case 2 : We can rearrange ‘S’ as “onetwonine” which implies “129”.
2
tsirxee
szixeoneor
36
016
Some alphabets are unique to some digits.
Here, we are going to use an observation that some alphabets are unique to some digits as illustrated below:
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.
O(N), where ‘N’ is the length of the string ‘S’.
We are iterating all characters one by one and incrementing the frequency.
O(1).
The total number of distinct characters is 26 (constant), and we are storing their frequencies, so, space complexity is O(1).