Dígitos cuyas representaciones alfabéticas están mezcladas en una string dada

Dada una string S de longitud N que es la representación en inglés de cualquier número de dígitos en el rango [0 – 9] en formato desordenado. La tarea es encontrar los dígitos de esta representación. 
Nota: Imprime los dígitos en cualquier orden

Ejemplos

Entrada: S = “owoftnuoer”
Salida: 124
Explicación: Los dígitos aquí son formas confusas de uno, dos y cuatro. Por lo tanto, la salida requerida puede ser 124 o 421 o 214, etc.

Entrada : S = “zesxrionezoreo”
Salida : 0016

Enfoque: este problema se puede resolver fácilmente al observar un hecho interesante: todos los dígitos pares tienen al menos un carácter que no está presente en ninguna otra string, mientras que todos los dígitos impares no:

Los siguientes dígitos tienen letras únicas:

• cero: único dígito con z
• dos: único dígito con w
• cuatro: único dígito con u
• seis: único dígito con x
• ocho: único dígito con g

Para los dígitos impares, cada letra también aparece en algún otro dígito. Los dígitos impares en palabras son {uno, tres, cinco, siete, nueve}. Siga los pasos que se indican a continuación para resolver el problema.

• Cree un vector de strings num que contendrá los números en letras inglesas del 0 al 9 y un vector de números enteros, count[] de tamaño 10 y también cree una string de respuesta ans para mostrar los números.
• Ahora, recorre la string dada de i = 0 a N-1 .
• Si s[i] = ‘z’ , aumente count[0] en 1 .
• Si s[i] = ‘w’ , aumente count[2] en 1 .
• Si s[i] = ‘g’ , aumente count[8] en 1 .
• Si s[i] = ‘x’ , aumente count[6] en 1 .
• Si s[i] = ‘v’ , aumente count[5] en 1 .
• Si s[i] = ‘o’ , aumente count[1] en 1 .
• Si s[i] = ‘s’ , aumente count[7] en 1 .
• Si s[i] = ‘f’ , aumente count[4] en 1 .
• Si s[i] = ‘h’ , aumente count[3] en 1 .
• Si s[i] = ‘i’ , aumente count[9] en 1 .
• Ahora, actualice los elementos del vector como se muestra a continuación:

• cuenta[7] = cuenta[7] – cuenta[6] .
• cuenta[5] = cuenta[5] – cuenta[7] .
• cuenta[4] = cuenta[4] – cuenta[5] .
• cuenta[1] = cuenta[1] – (cuenta[2] + cuenta[4] + cuenta[0]) .
• cuenta[3] = cuenta[3] – cuenta[8] .
• cuenta[9] = cuenta[9] – (cuenta[5] + cuenta[6] + cuenta[8]) .

• Ahora, recorra el vector de 0 a 9 y agregue el carácter (i + ‘0’) a ans , cuente [i] veces.
• Finalmente, escriba ans como la respuesta requerida.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to convert the jumbled
// string into digits
string finddigits(string s)
{
 
    // Strings of digits 0-9
    string num[]
        = { "zero", "one", "two",
            "three", "four", "five",
            "six", "seven", "eight", "nine" };
 
    // Initialize vector
    vector<int> arr(10);
 
    // Initialize answer
    string ans = "";
 
    // Size of the string
    int n = s.size();
 
    // Traverse the string
    for (int i = 0; i < n; i++) {
        if (s[i] == 'z')
            arr[0]++;
        if (s[i] == 'w')
            arr[2]++;
        if (s[i] == 'g')
            arr[8]++;
        if (s[i] == 'x')
            arr[6]++;
        if (s[i] == 'v')
            arr[5]++;
        if (s[i] == 'o')
            arr[1]++;
        if (s[i] == 's')
            arr[7]++;
        if (s[i] == 'f')
            arr[4]++;
        if (s[i] == 'h')
            arr[3]++;
        if (s[i] == 'i')
            arr[9]++;
    }
 
    // Update the elements of the vector
    arr[7] -= arr[6];
    arr[5] -= arr[7];
    arr[4] -= arr[5];
    arr[1] -= (arr[2] + arr[4] + arr[0]);
    arr[3] -= arr[8];
    arr[9] -= (arr[5] + arr[6] + arr[8]);
 
    // Print the digits into their
    // original format
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < arr[i]; j++) {
            ans += (char)(i + '0');
        }
    }
 
    // Return answer
    return ans;
}
 
// Driver Code
int main()
{
    string s = "owoftnuoer";
    cout << finddigits(s) << endl;
}

// Java program for the above approach
import java.io.*;
class GFG {
 
  // Function to convert the jumbled
  // string into digits
  static String finddigits(String s)
  {
 
    // Strings of digits 0-9
    String[] num
      = { "zero", "one", "two",   "three", "four",
         "five", "six", "seven", "eight", "nine" };
 
    // Initialize vector
    int[] arr = new int[10];
 
    // Initialize answer
    String ans = "";
 
    // Size of the string
    int n = s.length();
 
    // Traverse the string
    for (int i = 0; i < n; i++) {
      if (s.charAt(i) == 'z')
        arr[0]++;
      if (s.charAt(i) == 'w')
        arr[2]++;
      if (s.charAt(i) == 'g')
        arr[8]++;
      if (s.charAt(i) == 'x')
        arr[6]++;
      if (s.charAt(i) == 'v')
        arr[5]++;
      if (s.charAt(i) == 'o')
        arr[1]++;
      if (s.charAt(i) == 's')
        arr[7]++;
      if (s.charAt(i) == 'f')
        arr[4]++;
      if (s.charAt(i) == 'h')
        arr[3]++;
      if (s.charAt(i) == 'i')
        arr[9]++;
    }
 
    // Update the elements of the vector
    arr[7] -= arr[6];
    arr[5] -= arr[7];
    arr[4] -= arr[5];
    arr[1] -= (arr[2] + arr[4] + arr[0]);
    arr[3] -= arr[8];
    arr[9] -= (arr[5] + arr[6] + arr[8]);
 
    // Print the digits into their
    // original format
    for (int i = 0; i < 10; i++) {
      for (int j = 0; j < arr[i]; j++) {
        ans += (char)(i + '0');
      }
    }
 
    // Return answer
    return ans;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    String s = "owoftnuoer";
    System.out.println(finddigits(s));
  }
}
 
// This code is contributed by Dharanendra L V

# Python3 program for the above approach
 
# Function to convert the jumbled
# into digits
def finddigits(s):
     
    # Strings of digits 0-9
    num = [ "zero", "one", "two", "three",
            "four", "five", "six", "seven",
            "eight", "nine"]
 
    # Initialize vector
    arr = [0] * (10)
 
    # Initialize answer
    ans = ""
 
    # Size of the string
    n = len(s)
 
    # Traverse the string
    for i in range(n):
        if (s[i] == 'z'):
            arr[0] += 1
        if (s[i] == 'w'):
            arr[2] += 1
        if (s[i] == 'g'):
            arr[8] += 1
        if (s[i] == 'x'):
            arr[6] += 1
        if (s[i] == 'v'):
            arr[5] += 1
        if (s[i] == 'o'):
            arr[1] += 1
        if (s[i] == 's'):
            arr[7] += 1
        if (s[i] == 'f'):
            arr[4] += 1
        if (s[i] == 'h'):
            arr[3] += 1
        if (s[i] == 'i'):
            arr[9] += 1
             
    # Update the elements of the vector
    arr[7] -= arr[6]
    arr[5] -= arr[7]
    arr[4] -= arr[5]
    arr[1] -= (arr[2] + arr[4] + arr[0])
    arr[3] -= arr[8]
    arr[9] -= (arr[5] + arr[6] + arr[8])
 
    # Print the digits into their
    # original format
    for i in range(10):
        for j in range(arr[i]):
            ans += chr((i) + ord('0'))
 
    # Return answer
    return ans
 
# Driver Code
if __name__ == '__main__':
     
    s = "owoftnuoer"
     
    print(finddigits(s))
 
# This code is contributed by mohit kumar 29

// C# program for the above approach
using System;
public class GFG
{
 
  // Function to convert the jumbled
  // string into digits
  static string finddigits(string s)
  {
 
    // Initialize vector
    int[] arr = new int[10];
 
    // Initialize answer
    string ans = "";
 
    // Size of the string
    int n = s.Length;
 
    // Traverse the string
    for (int i = 0; i < n; i++) {
      if (s[i] == 'z')
        arr[0]++;
      if (s[i] == 'w')
        arr[2]++;
      if (s[i] == 'g')
        arr[8]++;
      if (s[i] == 'x')
        arr[6]++;
      if (s[i] == 'v')
        arr[5]++;
      if (s[i] == 'o')
        arr[1]++;
      if (s[i] == 's')
        arr[7]++;
      if (s[i] == 'f')
        arr[4]++;
      if (s[i] == 'h')
        arr[3]++;
      if (s[i] == 'i')
        arr[9]++;
    }
 
    // Update the elements of the vector
    arr[7] -= arr[6];
    arr[5] -= arr[7];
    arr[4] -= arr[5];
    arr[1] -= (arr[2] + arr[4] + arr[0]);
    arr[3] -= arr[8];
    arr[9] -= (arr[5] + arr[6] + arr[8]);
 
    // Print the digits into their
    // original format
    for (int i = 0; i < 10; i++) {
      for (int j = 0; j < arr[i]; j++) {
        ans += (char)(i + '0');
      }
    }
 
    // Return answer
    return ans;
  }
 
  // Driver Code
  static public void Main()
  {
    string s = "owoftnuoer";
    Console.WriteLine(finddigits(s));
  }
}
 
// This code is contributed by Dharanendra L V

<script>
 
// JavaScript program for the above approach
 
// Function to convert the jumbled
// string into digits
function finddigits(s)
{
 
    // Strings of digits 0-9
    let num = [ "zero", "one", "two",
            "three", "four", "five",
            "six", "seven", "eight", "nine" ];
 
    // Initialize vector
    let arr = new Array(10).fill(0);
 
    // Initialize answer
    let ans = "";
 
    // Size of the string
    let n = s.length;
 
    // Traverse the string
    for (let i = 0; i < n; i++) {
        if (s[i] == 'z')
            arr[0]++;
        if (s[i] == 'w')
            arr[2]++;
        if (s[i] == 'g')
            arr[8]++;
        if (s[i] == 'x')
            arr[6]++;
        if (s[i] == 'v')
            arr[5]++;
        if (s[i] == 'o')
            arr[1]++;
        if (s[i] == 's')
            arr[7]++;
        if (s[i] == 'f')
            arr[4]++;
        if (s[i] == 'h')
            arr[3]++;
        if (s[i] == 'i')
            arr[9]++;
    }
 
    // Update the elements of the vector
    arr[7] -= arr[6];
    arr[5] -= arr[7];
    arr[4] -= arr[5];
    arr[1] -= (arr[2] + arr[4] + arr[0]);
    arr[3] -= arr[8];
    arr[9] -= (arr[5] + arr[6] + arr[8]);
 
    // Print the digits into their
    // original format
 
    for (let i = 0; i < 10; i++) {
        for (let j = 0; j < arr[i]; j++) {
            ans += i;
        }
    }
 
    // Return answer
    return ans;
}
 
// Driver Code
 
let s = "owoftnuoer";
document.write(finddigits(s),"</br>");
 
// this code is contributed by shinjanpatra.
</script>

124

Complejidad de tiempo: O(N) donde N es la longitud de la string
Espacio auxiliar: O(N)