Genere un número en orden decreciente de frecuencias de caracteres de una string dada

Dada una string Str de longitud N , que consiste en letras minúsculas, la tarea es generar un número en orden decreciente de la frecuencia de caracteres en la string dada. Si dos caracteres tienen la misma frecuencia, el carácter con menor valor ASCII aparece primero. Los números asignados a los caracteres {a, b, …., y, z} son {1, 2, …., 25, 26} respectivamente. 
Nota: Para los caracteres que tienen asignados valores superiores a 9 , tome su módulo 10.
Ejemplos: 

Entrada: N = 6, Str = “aaabbd” 
Salida: 124 
Explicación: 
Los caracteres dados y sus respectivas frecuencias son: 

• un = 3
• segundo = 2
• re = 1

Dado que el número debe generarse en orden creciente de sus frecuencias, el número final generado es 124 .
Entrada: N = 6, Str = “akkzzz” 
Salida: 611 
Explicación: 
Los caracteres dados y sus respectivas frecuencias son: 

• un = 1
• k = 2
• z = 3

Para z , valor asignado = 26 
Por lo tanto, el dígito correspondiente asignado = 26 % 10 = 6 
Para k , valor asignado = 11 
Por lo tanto, el dígito correspondiente asignado = 11 % 10 = 1 
Dado que el número debe generarse en orden creciente de sus frecuencias, el número final generado es 611 . 

Enfoque: 
siga los pasos a continuación para resolver el problema: 

• Inicialice un mapa y almacene las frecuencias de cada carácter.
• Atraviese el mapa e inserte todos los pares { Carácter, Frecuencia } en un vector de par.
• Ordene este vector de tal manera que el par con mayor frecuencia aparezca primero y entre los pares que tienen la misma frecuencia, aquellos con menor valor ASCII aparezcan primero.
• Recorre este vector y encuentra el dígito correspondiente a cada carácter.
• Imprime el número final generado.

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

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Custom comparator for sorting
bool comp(pair<char, int>& p1,
          pair<char, int>& p2)
{
 
    // If frequency is same
    if (p1.second == p2.second)
 
        // Character with lower ASCII
        // value appears first
        return p1.first < p2.first;
 
    // Otherwise character with higher
    // frequency appears first
    return p1.second > p2.second;
}
 
// Function to sort map accordingly
string sort(map<char, int>& m)
{
 
    // Declaring vector of pairs
    vector<pair<char, int> > a;
 
    // Output string to store the result
    string out;
 
    // Traversing map and pushing
    // pairs to vector
    for (auto x : m) {
 
        a.push_back({ x.first, x.second });
    }
 
    // Using custom comparator
    sort(a.begin(), a.end(), comp);
 
    // Traversing the Vector
    for (auto x : a) {
 
        // Get the possible digit
        // from assigned value
        int k = x.first - 'a' + 1;
 
        // Ensures k does not exceed 9
        k = k % 10;
 
        // Append each digit
        out = out + to_string(k);
    }
 
    // Returning final result
    return out;
}
 
// Function to generate and return
// the required number
string formString(string s)
{
    // Stores the frequencies
    map<char, int> mp;
 
    for (int i = 0; i < s.length(); i++)
        mp[s[i]]++;
 
    // Sort map in required order
    string res = sort(mp);
 
    // Return the final result
    return res;
}
 
// Driver Code
int main()
{
    int N = 4;
 
    string Str = "akkzzz";
 
    cout << formString(Str);
 
    return 0;
}

# Python3 Program to implement
# the above approach
 
# Function to sort map
# accordingly
def sort(m):
 
    # Declaring vector
    # of pairs
    a = {}
 
    # Output string to
    # store the result
    out = ""
 
    # Traversing map and
    # pushing pairs to vector
    for x in m:
        a[x] = []
 
        a[x].append(m[x])
 
    # Character with lower ASCII
    # value appears first
    a = dict(sorted(a.items(),
                  key = lambda x : x[0]))
 
    # Character with higher
    # frequency appears first
    a = dict(sorted(a.items(),
                    reverse = True,
                    key = lambda x : x[1]))
 
    # Traversing the Vector
    for x in a:
 
        # Get the possible digit
        # from assigned value
        k = ord(x[0]) - ord('a') + 1
 
        # Ensures k does
        # not exceed 9
        k = k % 10
 
        # Append each digit
        out = out + str(k)
 
    # Returning final result
    return out
 
# Function to generate and return
# the required number
def formString(s):
 
    # Stores the frequencies
    mp = {}
    for i in range(len(s)):
        if s[i] in mp:
            mp[s[i]] += 1
        else:
            mp[s[i]] = 1
 
    # Sort map in
    # required order
    res = sort(mp)
 
    # Return the
    # final result
    return res
 
# Driver Code
N = 4
Str = "akkzzz"
print(formString(Str))
 
# This code is contributed by avanitrachhadiya2155

<script>
 
// JavaScript Program to implement
// the above approach
 
// Custom comparator for sorting
function comp(p1,p2)
{
 
    // If frequency is same
    if (p1[1] == p2[1])
 
        // Character with lower ASCII
        // value appears first
        return p2.charCodeAt(0) - p1.charCodeAt(0);
 
    // Otherwise character with higher
    // frequency appears first
    return p2[1] - p1[1];
}
 
// Function to sort map accordingly
function sort(m)
{
 
    // Declaring vector of pairs
    let a = [];
 
    // Output string to store the result
    let out="";
 
    // Traversing map and pushing
    // pairs to vector
    for (let [x,y] of m) {
 
        a.push([ x, y ]);
    }
 
    // Using custom comparator
    a.sort(comp);
 
    // Traversing the Vector
    for (let x of a) {
 
        // Get the possible digit
        // from assigned value
        let k = (x[0].charCodeAt(0) - 97 + 1)%10;
 
 
        // Append each digit
        out += k.toString();
    }
 
    // Returning final result
    return out;
}
 
// Function to generate and return
// the required number
function formString(s)
{
 
    // Stores the frequencies
    let mp = new Map();
 
    for (let i = 0; i < s.length; i++){
        if(mp.has(s[i])){
            mp.set(s[i],mp.get(s[i])+1);
        }
        else{
            mp.set(s[i],1);
        }
    }
 
    // Sort map in required order
    let res = sort(mp);
 
    // Return the final result
    return res;
}
 
// Driver Code
let N = 4;
let Str = "akkzzz";
document.write(formString(Str),"</br>");
 
// This code is contributed by shinjanpatra
 
</script>

611

Complejidad temporal: O(NlogN) 
Espacio auxiliar: O(N)