Find digits present in given jumbled String

Photo of Namachila Namachila Send an email 3 minutes ago
0 0 9 minutes read

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.
  • 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 string
string 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 program
int main()
{
    string s = "zerootwneozero";
    int N = s.size();
 
    // Function call
    cout << findNumber(s, N);
    return 0;
}
 

















Java


















 






 




 



























// Java code to implement the approach


import 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 string


def 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 program


 


s = "zerootwneozero"


N = len(s)


 


# Function call


print(findNumber(s, N))


 


# this code is contributed by shinjanpatra








































C#


















 






 




 



























// C# code to implement the approach


using 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 string


function 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 program


 


let s = "zerootwneozero"


let N = s.length


 


// Function call


document.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 zambiatek!







			
		


				

			

				

						
							Photo of Namachila
						
					Namachila
						
							
							Send an email
						
					3 minutes ago
0 0  9 minutes read 


		

					

		


		

		

		

		
	


	
	


		
		


								

						
							Photo of Namachila						
					

					
			


											
Namachila

						
				

									


							

			

		

		


	





			

			

	

				


					

						
Related Articles

					


					


					
							


								
			
								
Print all Strings from array A[] having all strings from array B[] as subsequence


								
3 minutes ago
							


						
							


								
			
								
Longest subsequence having difference between the maximum and minimum element equal to K


								
3 minutes ago
							


						
							


								
			
								
Construct a Maximum Binary Tree from two given Binary Trees


								
3 minutes ago
							


						
							


								
			
								
Maximize sum of averages of subsequences of lengths lying in a given range


								
3 minutes ago
							


						
					

				


				


		

		
	

		
Leave a Reply 
Your email address will not be published. Required fields are marked *
 
 



 


 


 


	

	

	



	


	




	

	
	
	






		

		
		
			
			Back to top button