Given a string s of length N, containing digits written in words but in jumbled form, the task is to find out the digits present in the string in word form and arrange them in sorted order.
Examples:
Input: s = “ozerotwneozero”
Output: 0012
Explanation: The string can be arranged as “zerozeroonetwo”.
Therefore the digits are 0, 0, 1 and 2.Input: s = “otwneotheer”
Output: 123
Approach: This problem can be solved using map based on the following idea:
Store the frequencies of each of the digits and then try the word representation of each of the digits starting from 0 to 9.
Follow the below steps to implement the idea:
- Take one string variable ans = “” and one map named as mp.
- Traverse string s and insert all the characters in map.
- Run loop for all the digit from 0 to 9
- Now check in map that all the character of alphabetical representation of that digit is present or not.
- If we found all the characters of zero then append that digit as char in ans.
- Check again for the same until no more same digit is found.
- Now check in map that all the character of alphabetical representation of that digit is present or not.
- Return ans.
Below is the code of the above implementation:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to find the digits present// in a stringstring findNumber(string S, int N){ // Stores the final ans string ans = ""; // Stores the corresponding character // from the word map<char, int> mp; for (int i = 0; i < N; i++) { mp[S[i]]++; } while (mp['z'] && mp['e'] && mp['r'] && mp['o']) { mp['z']--; mp['e']--; mp['r']--; mp['o']--; ans += '0'; } while (mp['o'] && mp['n'] && mp['e']) { mp['o']--; mp['n']--; mp['e']--; ans += '1'; } while (mp['t'] && mp['w'] && mp['o']) { mp['t']--; mp['w']--; mp['o']--; ans += '2'; } while (mp['t'] && mp['h'] && mp['r'] && mp['e'] && mp['e']) { mp['t']--; mp['h']--; mp['r']--; mp['e']--; mp['e']--; ans += '3'; } while (mp['f'] && mp['o'] && mp['u'] && mp['r']) { mp['f']--; mp['o']--; mp['u']--; mp['r']--; ans += '4'; } while (mp['f'] && mp['i'] && mp['v'] && mp['e']) { mp['f']--; mp['i']--; mp['v']--; mp['e']--; ans += '5'; } while (mp['s'] && mp['i'] && mp['x']) { mp['s']--; mp['i']--; mp['x']--; ans += '6'; } while (mp['s'] && mp['e'] && mp['v'] && mp['e'] && mp['n']) { mp['s']--; mp['e']--; mp['v']--; mp['e']--; mp['n']--; ans += '7'; } while (mp['e'] && mp['i'] && mp['g'] && mp['h'] && mp['t']) { mp['e']--; mp['i']--; mp['g']--; mp['h']--; mp['t']--; ans += '8'; } while (mp['n'] && mp['i'] && mp['n'] && mp['e']) { mp['n']--; mp['i']--; mp['n']--; mp['e']--; ans += '9'; } return ans;}// Driver programint main(){ string s = "zerootwneozero"; int N = s.size(); // Function call cout << findNumber(s, N); return 0;} |
Java
// Java code to implement the approachimport java.io.*;import java.util.*;class GFG { // Function to find the digits present // in a string public static String findNumber(String S, int N) { // Stores the final ans String ans = ""; // Stores the corresponding character // from the word TreeMap<Character, Integer> mp = new TreeMap<Character, Integer>(); for (int i = 0; i < N; i++) { if (mp.get(S.charAt(i)) != null) mp.put(S.charAt(i), mp.get(S.charAt(i)) + 1); else mp.put(S.charAt(i), 1); } for (char i = 'a'; i < 'z'; i++) { if (mp.get(i) == null) mp.put(i, 0); } while (mp.get('z') != 0 && mp.get('e') != 0 && mp.get('r') != 0 && mp.get('o') != 0) { mp.put('z', mp.get('z') - 1); mp.put('e', mp.get('e') - 1); mp.put('r', mp.get('r') - 1); mp.put('o', mp.get('o') - 1); ans += '0'; } while (mp.get('o') != 0 && mp.get('n') != 0 && mp.get('e') != 0) { mp.put('o', mp.get('o') - 1); mp.put('n', mp.get('n') - 1); mp.put('e', mp.get('e') - 1); ans += '1'; } while (mp.get('t') != 0 && mp.get('w') != 0 && mp.get('o') != 0) { mp.put('t', mp.get('t') - 1); mp.put('w', mp.get('w') - 1); mp.put('o', mp.get('o') - 1); ans += '2'; } while (mp.get('t') != 0 && mp.get('h') != 0 && mp.get('r') != 0 && mp.get('e') != 0 && mp.get('e') != 0) { mp.put('t', mp.get('t') - 1); mp.put('h', mp.get('h') - 1); mp.put('r', mp.get('r') - 1); mp.put('e', mp.get('e') - 1); mp.put('e', mp.get('e') - 1); ans += '3'; } while (mp.get('f') != 0 && mp.get('o') != 0 && mp.get('u') != 0 && mp.get('r') != 0) { mp.put('f', mp.get('f') - 1); mp.put('o', mp.get('o') - 1); mp.put('u', mp.get('u') - 1); mp.put('r', mp.get('r') - 1); ans += '4'; } while (mp.get('f') != 0 && mp.get('i') != 0 && mp.get('v') != 0 && mp.get('e') != 0) { mp.put('f', mp.get('f') - 1); mp.put('i', mp.get('i') - 1); mp.put('v', mp.get('v') - 1); mp.put('e', mp.get('e') - 1); ans += '5'; } while (mp.get('s') != 0 && mp.get('i') != 0 && mp.get('x') != 0) { mp.put('s', mp.get('s') - 1); mp.put('i', mp.get('i') - 1); mp.put('x', mp.get('x') - 1); ans += '6'; } while (mp.get('s') != 0 && mp.get('e') != 0 && mp.get('v') != 0 && mp.get('e') != 0 && mp.get('n') != 0) { mp.put('s', mp.get('s') - 1); mp.put('e', mp.get('e') - 1); mp.put('v', mp.get('v') - 1); mp.put('e', mp.get('e') - 1); mp.put('n', mp.get('n') - 1); ans += '7'; } while (mp.get('e') != 0 && mp.get('i') != 0 && mp.get('g') != 0 && mp.get('h') != 0 && mp.get('t') != 0) { mp.put('e', mp.get('e') - 1); mp.put('i', mp.get('i') - 1); mp.put('g', mp.get('g') - 1); mp.put('h', mp.get('h') - 1); mp.put('t', mp.get('t') - 1); ans += '8'; } while (mp.get('n') != 0 && mp.get('i') != 0 && mp.get('n') != 0 && mp.get('e') != 0) { mp.put('n', mp.get('n') - 1); mp.put('i', mp.get('i') - 1); mp.put('n', mp.get('n') - 1); mp.put('e', mp.get('e') - 1); ans += '9'; } return ans; } // Driver Code public static void main(String[] args) { String s = "zerootwneozero"; int N = s.length(); // Function call System.out.print(findNumber(s, N)); }}// This code is contributed by Rohit Pradhan |
Python3
# Python code to implement the approach# Function to find the digits present# in a stringdef findNumber(S, N): # Stores the final ans ans = "" # Stores the corresponding character # from the word mp = {} for i in range(N): if S[i] in mp: mp[S[i]] += 1 else: mp[S[i]] = 1 while ('z' in mp and 'e' in mp and 'r' in mp and 'o' in mp and mp['z'] and mp['e'] and mp['r'] and mp['o']): mp['z'] -= 1 mp['e'] -= 1 mp['r'] -= 1 mp['o'] -= 1 ans += '0' while ('o' in mp and 'n' in mp and 'e' in mp and mp['o'] and mp['n'] and mp['e']): mp['o'] -= 1 mp['n'] -= 1 mp['e'] -= 1 ans += '1' while ('t' in mp and 'w' in mp and 'o' in mp and mp['t'] and mp['w'] and mp['o']): mp['t'] -= 1 mp['w'] -= 1 mp['o'] -= 1 ans += '2' while ('t' in mp and 'h' in mp and 'r' in mp and 'e' in mp and 'e' in mp and mp['t'] and mp['h'] and mp['r'] and mp['e'] and mp['e']): mp['t'] -= 1 mp['h'] -= 1 mp['r'] -= 1 mp['e'] -= 1 mp['e'] -= 1 ans += '3' while ('f' in mp and 'o' in mp and 'u' in mp and 'r' in mp and mp['f'] and mp['o'] and mp['u'] and mp['r']): mp['f'] -= 1 mp['o'] -= 1 mp['u'] -= 1 mp['r'] -= 1 ans += '4' while ('f' in mp and 'i' in mp and 'v' in mp and 'e' in mp and mp['f'] and mp['i'] and mp['v'] and mp['e']): mp['f'] -= 1 mp['i'] -= 1 mp['v'] -= 1 mp['e'] -= 1 ans += '5' while ('s' in mp and 'i' in mp and 'x' in mp and mp['s'] and mp['i'] and mp['x']): mp['s'] -= 1 mp['i'] -= 1 mp['x'] -= 1 ans += '6' while ('s' in mp and 'e' in mp and 'v' in mp and 'e' in mp and 'n' in mp and mp['s'] and mp['e'] and mp['v'] and mp['e'] and mp['n']): mp['s'] -= 1 mp['e'] -= 1 mp['v'] -= 1 mp['e'] -= 1 mp['n'] -= 1 ans += '7' while ('e' in mp and 'i' in mp and 'g' in mp and 'h' in mp and 't' in mp and mp['e'] and mp['i'] and mp['g'] and mp['h'] and mp['t']): mp['e'] -= 1 mp['i'] -= 1 mp['g'] -= 1 mp['h'] -= 1 mp['t'] -= 1 ans += '8' while ('n' in mp and 'i' in mp and 'n' in mp and 'e' in mp and mp['n'] and mp['i'] and mp['n'] and mp['e']): mp['n'] -= 1 mp['i'] -= 1 mp['n'] -= 1 mp['e'] -= 1 ans += '9' return ans# Driver programs = "zerootwneozero"N = len(s)# Function callprint(findNumber(s, N))# this code is contributed by shinjanpatra |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;public class GFG{ // Function to find the digits present // in a string static string findNumber(string S, int N) { // Stores the final ans string ans = ""; // Stores the corresponding character // from the word IDictionary<char, int> mp = new Dictionary<char, int>(); //Initializing the map string letters = "abcdefghijklmnopqrstuvwxyz"; for (int i = 0; i < 26; i++) { if (!mp.ContainsKey(letters[i])) mp[letters[i]] = 0; } //building the map from the given string for (int i = 0; i < N; i++) { mp[S[i]]++; } //updating the map based on the conditions //in the question while (mp['z'] * mp['e'] * mp['r'] * mp['o'] != 0) { mp['z']--; mp['e']--; mp['r']--; mp['o']--; ans += '0'; } while (mp['o'] * mp['n'] * mp['e'] != 0) { mp['o']--; mp['n']--; mp['e']--; ans += '1'; } while (mp['t'] * mp['w'] * mp['o'] != 0) { mp['t']--; mp['w']--; mp['o']--; ans += '2'; } while (mp['t'] * mp['h'] * mp['r'] * mp['e'] * mp['e'] != 0) { mp['t']--; mp['h']--; mp['r']--; mp['e']--; mp['e']--; ans += '3'; } while (mp['f'] * mp['o'] * mp['u'] * mp['r'] != 0) { mp['f']--; mp['o']--; mp['u']--; mp['r']--; ans += '4'; } while (mp['f'] * mp['i'] * mp['v'] * mp['e'] != 0) { mp['f']--; mp['i']--; mp['v']--; mp['e']--; ans += '5'; } while (mp['s'] * mp['i'] * mp['x'] != 0) { mp['s']--; mp['i']--; mp['x']--; ans += '6'; } while (mp['s'] * mp['e'] * mp['v'] * mp['e'] * mp['n'] != 0) { mp['s']--; mp['e']--; mp['v']--; mp['e']--; mp['n']--; ans += '7'; } while (mp['e'] * mp['i'] * mp['g'] * mp['h'] * mp['t'] != 0) { mp['e']--; mp['i']--; mp['g']--; mp['h']--; mp['t']--; ans += '8'; } while (mp['n'] * mp['i'] * mp['n'] * mp['e'] != 0) { mp['n']--; mp['i']--; mp['n']--; mp['e']--; ans += '9'; } return ans; } // Driver code public static void Main(string[] args) { string s = "zerootwneozero"; int N = s.Length; // Function call Console.WriteLine(findNumber(s, N)); }}//This code is contributed by phasing17 |
Javascript
<script>// JavaScript code to implement the approach// Function to find the digits present// in a stringfunction findNumber(S, N){ // Stores the final ans let ans = "" // Stores the corresponding character // from the word let mp = new Map() for(let i=0;i<N;i++){ if(mp.has(S[i])) mp.set(S[i], mp.get(S[i])+ 1) else mp.set(S[i],1) } while (mp.has('z') && mp.has('e') && mp.has('r') && mp.has('o') && mp.get('z')>0 && mp.get('e')>0 && mp.get('r')>0 && mp.get('o')>0){ mp.set('z',mp.get('z')-1); mp.set('e',mp.get('e')-1); mp.set('r',mp.get('r')-1); mp.set('o',mp.get('o')-1); ans += '0' } while (mp.has('o') && mp.has('n') && mp.has('e') && mp.get('o')>0 && mp.get('n')>0 && mp.get('e')>0){ mp.set('o',mp.get('o')-1); mp.set('n',mp.get('n')-1); mp.set('e',mp.get('e')-1); ans += '1' } while (mp.has('t') && mp.has('w') && mp.has('o') && mp.get('t')>0 && mp.get('w')>0 && mp.get('o')>0){ mp.set('t',mp.get('t')-1); mp.set('w',mp.get('w')-1); mp.set('o',mp.get('o')-1); ans += '2' } while (mp.has('t') && mp.has('h') && mp.has('r') && mp.has('e') && mp.has('e') && mp.get('t')>0 && mp.get('h')>0 && mp.get('r')>0 && mp.get('e')>0 && mp.get('e')>0){ mp.set('t',mp.get('t')-1); mp.set('h',mp.get('h')-1); mp.set('r',mp.get('r')-1); mp.set('e',mp.get('e')-1); mp.set('e',mp.get('e')-1); ans += '3' } while (mp.has('f') && mp.has('o') && mp.has('u') && mp.has('r') && mp.get('f')>0 && mp.get('o')>0 && mp.get('u')>0 && mp.get('r')>0){ mp.set('f',mp.get('f')-1); mp.set('o',mp.get('o')-1); mp.set('u',mp.get('u')-1); mp.set('r',mp.get('r')-1); ans += '4' } while (mp.has('f') && mp.has('i') && mp.has('v') && mp.has('e') && mp.get('f')>0 && mp.get('i')>0 && mp.get('v')>0 && mp.get('e')>0){ mp.set('f',mp.get('f')-1); mp.set('i',mp.get('i')-1); mp.set('v',mp.get('v')-1); mp.set('e',mp.get('e')-1); ans += '5' } while (mp.has('s') && mp.has('i') && mp.has('x') && mp.get('s')>0 && mp.get('i')>0 && mp.get('x')>0){ mp.set('s',mp.get('s')-1); mp.set('i',mp.get('i')-1); mp.set('x',mp.get('x')-1); ans += '6' } while (mp.has('s') && mp.has('e') && mp.has('v') && mp.has('e') && mp.has('n') && mp.get('s')>0 && mp.get('e')>0 && mp.get('v')>0 && mp.get('e')>0 && mp.get('n')>0){ mp.set('s',mp.get('s')-1) mp.set('e',mp.get('e')-1) mp.set('v',mp.get('v')-1) mp.set('e',mp.get('e')-1) mp.set('n',mp.get('n')-1) ans += '7' } while (mp.has('e') && mp.has('i') && mp.has('g') && mp.has('h') && mp.has('t') && mp.get('e')>0 && mp.get('i')>0 && mp.get('g')>0 && mp.get('h')>0 && mp.get('t')>0){ mp.set('e',mp.get('e')-1); mp.set('i',mp.get('i')-1); mp.set('g',mp.get('g')-1); mp.set('h',mp.get('h')-1); mp.set('t',mp.get('t')-1); ans += '8' } while (mp.has('n') && mp.has('i') && mp.has('n') && mp.has('e') && mp.get('n')>0 && mp.get('i')>0 && mp.get('n')>0 && mp.get('e')>0){ mp.set('n',mp.get('n')-1); mp.set('i',mp.get('i')-1); mp.set('n',mp.get('n')-1); mp.set('e',mp.get('e')-1); ans += '9' } return ans}// Driver programlet s = "zerootwneozero"let N = s.length// Function calldocument.write(findNumber(s, N))// this code is contributed by shinjanpatra</script> |
Output
0012
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
