Imprimir caracteres en orden decreciente de frecuencia

Dada la string str , la tarea es imprimir los caracteres en orden decreciente de su frecuencia. Si la frecuencia de dos caracteres es la misma, ordénelos alfabéticamente en orden descendente.
Ejemplos: 
 

Entrada: str = “geeksforgeeks” 
Salida: 
e – 4 
s – 2 
k – 2 
g – 2 
r – 1 
o – 1 
f – 1
Entrada: str = “bbcc” 
Salida: 
c – 2 
b – 2
 

Enfoque 1: 
 

• Use un mapa_desordenado para almacenar las frecuencias de todos los elementos de la string dada.
• Encuentre el elemento de frecuencia máxima del mapa, imprímalo con su frecuencia y elimínelo del mapa.
• Repita el paso anterior mientras el mapa no esté vacío.

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

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to print the characters
// of the given string in decreasing
// order of their frequencies
void printChar(string str, int len)
{
 
    // To store the
    unordered_map<char, int> occ;
    for (int i = 0; i < len; i++)
        occ[str[i]]++;
 
    // Map's size
    int size = occ.size();
    unordered_map<char, int>::iterator it;
 
    // While there are elements in the map
    while (size--) {
 
        // Finding the maximum value
        // from the map
        unsigned currentMax = 0;
        char arg_max;
        for (it = occ.begin(); it != occ.end(); ++it) {
            if (it->second > currentMax
                || (it->second == currentMax
                    && it->first > arg_max)) {
                arg_max = it->first;
                currentMax = it->second;
            }
        }
 
        // Print the character
        // alongwith its frequency
        cout << arg_max << " - " << currentMax << endl;
 
        // Delete the maximum value
        occ.erase(arg_max);
    }
}
 
// Driver code
int main()
{
 
    string str = "geeksforgeeks";
    int len = str.length();
 
    printChar(str, len);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
class GFG{
 
// Function to print the characters
// of the given String in decreasing
// order of their frequencies
static void printChar(char []arr, int len)
{
 
    // To store the
    HashMap<Character,
              Integer> occ = new HashMap<Character,
                                         Integer>();
    for (int i = 0; i < len; i++)
        if(occ.containsKey(arr[i]))
        {
            occ.put(arr[i], occ.get(arr[i]) + 1);
        }
          else
        {
            occ.put(arr[i], 1);
        }
 
    // Map's size
    int size = occ.size();
 
    // While there are elements in the map
    while (size-- > 0)
    {
 
        // Finding the maximum value
        // from the map
        int currentMax = 0;
        char arg_max = 0;
        for (Map.Entry<Character,
                        Integer> it : occ.entrySet())
        {
            if (it.getValue() > currentMax ||
               (it.getValue() == currentMax &&
                it.getKey() > arg_max))
            {
                arg_max = it.getKey();
                currentMax = it.getValue();
            }
        }
 
        // Print the character
        // alongwith its frequency
        System.out.print(arg_max + " - " +
                         currentMax + "\n");
 
        // Delete the maximum value
        occ.remove(arg_max);
    }
}
 
// Driver code
public static void main(String[] args)
{
    String str = "geeksforgeeks";
    int len = str.length();
 
    printChar(str.toCharArray(), len);
}
}
 
// This code is contributed by gauravrajput1

# Python implementation of the approach
 
# Function to print the characters
# of the given String in decreasing
# order of their frequencies
def printChar(arr, Len):
 
    # To store the
    occ = {}
    for i in range(Len):
         
        if(arr[i] in occ):
            occ[arr[i]] = occ[arr[i]] + 1
         
        else:
            occ[arr[i]] = 1
  
    # Map's size
    size = len(occ)
  
    # While there are elements in the map
    while (size > 0):
  
        # Finding the maximum value
        # from the map
        currentMax = 0
        arg_max = 0
        for key, value in occ.items():
 
            if (value > currentMax or (value == currentMax and key > arg_max)):
                arg_max = key
                currentMax = value
  
        # Print the character
        # alongwith its frequency
        print(f"{arg_max} - {currentMax}")
  
        # Delete the maximum value
        occ.pop(arg_max)
        size -= 1
 
# Driver code
Str = "geeksforgeeks"
Len = len(Str)
 
 
printChar(list(Str), Len)
 
# This code is contributed by shinjanpatra

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to print the characters
// of the given String in decreasing
// order of their frequencies
static void printChar(char []arr, int len)
{
 
    // To store the
    Dictionary<char,
               int> occ = new Dictionary<char,
                                         int>();
    for (int i = 0; i < len; i++)
        if(occ.ContainsKey(arr[i]))
        {
            occ[arr[i]]  = occ[arr[i]] + 1;
        }
          else
        {
            occ.Add(arr[i], 1);
        }
 
    // Map's size
    int size = occ.Count;
 
    // While there are elements in the map
    while (size-- > 0)
    {
 
        // Finding the maximum value
        // from the map
        int currentMax = 0;
        char arg_max = (char)0;
        foreach (KeyValuePair<char, int> it in occ)
        {
            if (it.Value > currentMax ||
               (it.Value == currentMax &&
                it.Key > arg_max))
            {
                arg_max = it.Key;
                currentMax = it.Value;
            }
        }
 
        // Print the character
        // alongwith its frequency
        Console.Write(arg_max + " - " +
                      currentMax + "\n");
 
        // Delete the maximum value
        occ.Remove(arg_max);
    }
}
 
// Driver code
public static void Main(String[] args)
{
    String str = "geeksforgeeks";
    int len = str.Length;
 
    printChar(str.ToCharArray(), len);
}
}
 
// This code is contributed by Princi Singh

<script>
// Javascript implementation of the approach
 
// Function to print the characters
// of the given String in decreasing
// order of their frequencies
function printChar(arr, len)
{
 
    // To store the
    let  occ = new Map();
    for (let i = 0; i < len; i++)
        if(occ.has(arr[i]))
        {
            occ.set(arr[i], occ.get(arr[i]) + 1);
        }
          else
        {
            occ.set(arr[i], 1);
        }
  
    // Map's size
    let size = occ.size;
  
    // While there are elements in the map
    while (size-- > 0)
    {
  
        // Finding the maximum value
        // from the map
        let currentMax = 0;
        let arg_max = 0;
        for (let [key, value] of occ.entries())
        {
            if (value > currentMax ||
               (value == currentMax &&
                key > arg_max))
            {
                arg_max = key;
                currentMax = value;
            }
        }
  
        // Print the character
        // alongwith its frequency
        document.write(arg_max + " - " +
                         currentMax + "<br>");
  
        // Delete the maximum value
        occ.delete(arg_max);
    }
}
 
// Driver code
let str = "geeksforgeeks";
let len = str.length;
 
printChar(str.split(""), len);
 
// This code is contributed by patel2127
</script>

e - 4
s - 2
k - 2
g - 2
r - 1
o - 1
f - 1

Enfoque 2: Haremos una array arr de tamaño uno más que el tamaño de la longitud de string dada en la que almacenaremos la Lista de caracteres cuya frecuencia es igual al índice de arr y seguiremos los pasos a continuación:

• Haz un mapa de frecuencia usando una array de caracteres presentes en la string dada.
• Array de frecuencia transversal, si su valor es mayor que cero, digamos k.
• En el índice kth de arr , almacene su valor de carácter en la Lista en el índice 0 (ya que necesitamos el orden descendente de los alfabetos si la frecuencia es la misma).
• Traverse arr desde atrás, ya que primero necesitamos una mayor frecuencia si la Lista en ese índice no está vacía, imprima su frecuencia y carácter.

Implementación del enfoque anterior:

// Java implementation of above approach
import java.util.*;
 
class GFG {
    // Driver Code
    public static void main(String[] args)
    {
        String str = "geeksforgeeks";
        printChar(str);
    }
    @SuppressWarnings("unchecked")
    // Function to print the characters
    // of the given string in decreasing
    // order of their frequencies
    public static void printChar(String str)
    {
        // Initializing array of List type.
        List<Character>[] arr = new List[str.length() + 1];
        for (int i = 0; i <= str.length(); i++) {
            // Initializing List of type Character.
            arr[i] = new ArrayList<>();
        }
        int[] freq = new int[256];
        // Mapking frequency map
        for (int i = 0; i < str.length(); i++) {
            freq[(char)str.charAt(i)]++;
        }
        // Traversing frequency array
        for (int i = 0; i < 256; i++) {
            if (freq[i] > 0) {
                // If frequency array is greater than zero
                // then storing its character on
                // i-th(frequency of that character) index
                // of arr
                arr[freq[i]].add(0, (char)(i));
            }
        }
        // Traversing arr from backwards as we need greater
        // frequency character first
        for (int i = arr.length - 1; i >= 0; i--) {
            if (!arr[i].isEmpty()) {
                for (char ch : arr[i]) {
                    System.out.println(ch + "-" + i);
                }
            }
        }
    }
}

e-4
s-2
k-2
g-2
r-1
o-1
f-1

Complejidad de tiempo: O (n), n es la longitud de la string dada

Espacio Auxiliar : O(n)