Caracteres mínimos requeridos para ser eliminados para que la frecuencia de cada carácter sea única

Dada la string str , la tarea es encontrar el recuento mínimo de caracteres que deben eliminarse de la string de modo que la frecuencia de cada carácter de la string sea única.

Ejemplos:

Entrada: str = “ceabaacb”
Salida: 2
Explicación:
Las frecuencias de cada carácter distinto son las siguientes:
c —> 2
e —> 1
a —> 3
b —> 2
Formas posibles de hacer que la frecuencia de cada carácter sea única por número mínimo de movimientos son:

Eliminar ambas apariciones de ‘c’ modifica str a «eabaab»

Eliminar una aparición de ‘c’ y ‘e’ modifica str a «abaacb»

Por lo tanto, las eliminaciones mínimas requeridas son 2.

Entrada: S = “abbbcccd”
Salida: 2

Enfoque: El problema se puede resolver usando la técnica Greedy . La idea es usar Map y Priority Queue . Siga los pasos a continuación para resolver el problema:

Inicialice un mapa , digamos mp , para almacenar la frecuencia de cada carácter distinto de la string .
Inicialice una variable, digamos cntChar para almacenar la cantidad de caracteres necesarios para eliminar para que la frecuencia de cada carácter de la string sea única.
Cree una cola de prioridad , digamos pq , para almacenar la frecuencia de cada carácter de modo que la mayor frecuencia obtenida esté presente en la parte superior de la cola de prioridad pq .
Itere sobre la cola de prioridad hasta que pq esté vacío y verifique si el elemento superior de pq es igual al segundo elemento superior de pq o no. Si se determina que es cierto, disminuya el valor del elemento superior de pq en 1 e incremente el valor de cntChar en 1 .
De lo contrario, haga estallar el elemento superior de pq .
Finalmente, imprima el valor de cntChar .

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

C++

// C++ program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum count of
// characters required to be deleted to make
// frequencies of all characters unique
int minCntCharDeletionsfrequency(string& str,
                                 int N)
{
    // Stores frequency of each
    // distinct character of str
    unordered_map<char, int> mp;
 
    // Store frequency of each distinct
    // character such that the largest
    // frequency is present at the top
    priority_queue<int> pq;
 
    // Stores minimum count of characters
    // required to be deleted to make
    // frequency of each character unique
    int cntChar = 0;
 
    // Traverse the string
    for (int i = 0; i < N; i++) {
 
        // Update frequency of str[i]
        mp[str[i]]++;
    }
 
    // Traverse the map
    for (auto it : mp) {
 
        // Insert current
        // frequency into pq
        pq.push(it.second);
    }
 
    // Traverse the priority_queue
    while (!pq.empty()) {
 
        // Stores topmost
        // element of pq
        int frequent
            = pq.top();
 
        // Pop the topmost element
        pq.pop();
 
        // If pq is empty
        if (pq.empty()) {
 
            // Return cntChar
            return cntChar;
        }
 
        // If frequent and topmost
        // element of pq are equal
        if (frequent == pq.top()) {
 
            // If frequency of the topmost
            // element is greater than 1
            if (frequent > 1) {
 
                // Insert the decremented
                // value of frequent
                pq.push(frequent - 1);
            }
 
            // Update cntChar
            cntChar++;
        }
    }
 
    return cntChar;
}
 
// Driver Code
int main()
{
 
    string str = "abbbcccd";
 
    // Stores length of str
    int N = str.length();
    cout << minCntCharDeletionsfrequency(
        str, N);
    return 0;
}

Java

// Java program to implement
// the above approach
import java.util.*;
class GFG{
 
// Function to find the minimum count of
// characters required to be deleted to make
// frequencies of all characters unique
static int minCntCharDeletionsfrequency(char[] str,
                                        int N)
{
  // Stores frequency of each
  // distinct character of str
  HashMap<Character,
          Integer> mp =
          new HashMap<>();
 
  // Store frequency of each distinct
  // character such that the largest
  // frequency is present at the top
  PriorityQueue<Integer> pq =
          new PriorityQueue<>((x, y) ->
          Integer.compare(y, x));
 
  // Stores minimum count of characters
  // required to be deleted to make
  // frequency of each character unique
  int cntChar = 0;
 
  // Traverse the String
  for (int i = 0; i < N; i++)
  {
    // Update frequency of str[i]
    if(mp.containsKey(str[i]))
    {
      mp.put(str[i],
      mp.get(str[i]) + 1);
    }
    else
    {
      mp.put(str[i], 1);
    }
  }
 
  // Traverse the map
  for (Map.Entry<Character,
                 Integer> it :
                 mp.entrySet())
  {
    // Insert current
    // frequency into pq
    pq.add(it.getValue());
  }
 
  // Traverse the priority_queue
  while (!pq.isEmpty())
  {
    // Stores topmost
    // element of pq
    int frequent = pq.peek();
 
    // Pop the topmost element
    pq.remove();
 
    // If pq is empty
    if (pq.isEmpty()) {
 
      // Return cntChar
      return cntChar;
    }
 
    // If frequent and topmost
    // element of pq are equal
    if (frequent == pq.peek())
    {
      // If frequency of the topmost
      // element is greater than 1
      if (frequent > 1)
      {
        // Insert the decremented
        // value of frequent
        pq.add(frequent - 1);
      }
 
      // Update cntChar
      cntChar++;
    }
  }
 
  return cntChar;
}
 
// Driver Code
public static void main(String[] args)
{
  String str = "abbbcccd";
 
  // Stores length of str
  int N = str.length();
  System.out.print(minCntCharDeletionsfrequency(
         str.toCharArray(), N));
}
}
 
// This code is contributed by Rajput-Ji

Python3

# Python3 program to implement
# the above approach
 
# Function to find the minimum count of
# characters required to be deleted to make
# frequencies of all characters unique
def minCntCharDeletionsfrequency(str, N):
     
    # Stores frequency of each
    # distinct character of str
    mp = {}
 
    # Store frequency of each distinct
    # character such that the largest
    # frequency is present at the top
    pq = []
 
    # Stores minimum count of characters
    # required to be deleted to make
    # frequency of each character unique
    cntChar = 0
 
    # Traverse the string
    for i in range(N):
         
        # Update frequency of str[i]
        mp[str[i]] = mp.get(str[i], 0) + 1
         
    # Traverse the map
    for it in mp:
         
        # Insert current
        # frequency into pq
        pq.append(mp[it])
 
    pq = sorted(pq)
     
    # Traverse the priority_queue
    while (len(pq) > 0):
         
        # Stores topmost
        # element of pq
        frequent = pq[-1]
 
        # Pop the topmost element
        del pq[-1]
 
        # If pq is empty
        if (len(pq) == 0):
             
            # Return cntChar
            return cntChar
             
        # If frequent and topmost
        # element of pq are equal
        if (frequent == pq[-1]):
             
            # If frequency of the topmost
            # element is greater than 1
            if (frequent > 1):
                 
                # Insert the decremented
                # value of frequent
                pq.append(frequent - 1)
                 
            # Update cntChar
            cntChar += 1
             
        pq = sorted(pq)
         
    return cntChar
 
# Driver Code
if __name__ == '__main__':
     
    str = "abbbcccd"
 
    # Stores length of str
    N = len(str)
     
    print(minCntCharDeletionsfrequency(str, N))
 
# This code is contributed by mohit kumar 29

C#

// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to find the minimum count of
// characters required to be deleted to make
// frequencies of all characters unique
static int minCntCharDeletionsfrequency(char[] str,
                                        int N)
{
     
    // Stores frequency of each
    // distinct character of str
    Dictionary<char,
               int> mp = new Dictionary<char,
                                        int>();
 
    // Store frequency of each distinct
    // character such that the largest
    // frequency is present at the top
    List<int> pq = new List<int>();
 
    // Stores minimum count of characters
    // required to be deleted to make
    // frequency of each character unique
    int cntChar = 0;
 
    // Traverse the String
    for(int i = 0; i < N; i++)
    {
         
        // Update frequency of str[i]
        if (mp.ContainsKey(str[i]))
        {
            mp[str[i]]++;
        }
        else
        {
            mp.Add(str[i], 1);
        }
    }
 
    // Traverse the map
    foreach(KeyValuePair<char, int> it in mp)
    {
         
        // Insert current
        // frequency into pq
        pq.Add(it.Value);
    }
    pq.Sort();
    pq.Reverse();
     
    // Traverse the priority_queue
    while (pq.Count != 0)
    {
         
        // Stores topmost
        // element of pq
        pq.Sort();
        pq.Reverse();
        int frequent = pq[0];
 
        // Pop the topmost element
        pq.RemoveAt(0);
 
        // If pq is empty
        if (pq.Count == 0)
        {
             
            // Return cntChar
            return cntChar;
        }
 
        // If frequent and topmost
        // element of pq are equal
        if (frequent == pq[0])
        {
             
            // If frequency of the topmost
            // element is greater than 1
            if (frequent > 1)
            {
                 
                // Insert the decremented
                // value of frequent
                pq.Add(frequent - 1);
                pq.Sort();
                // pq.Reverse();
            }
 
            // Update cntChar
            cntChar++;
        }
    }
    return cntChar;
}
 
// Driver Code
public static void Main(String[] args)
{
    String str = "abbbcccd";
 
    // Stores length of str
    int N = str.Length;
     
    Console.Write(minCntCharDeletionsfrequency(
        str.ToCharArray(), N));
}
}
 
// This code is contributed by shikhasingrajput

Javascript

<script>
// Javascript program to implement
// the above approach
 
// Function to find the minimum count of
// characters required to be deleted to make
// frequencies of all characters unique
function minCntCharDeletionsfrequency(str,N)
{
    // Stores frequency of each
  // distinct character of str
  let mp = new Map();
  
  // Store frequency of each distinct
  // character such that the largest
  // frequency is present at the top
  let pq =[];
  
  // Stores minimum count of characters
  // required to be deleted to make
  // frequency of each character unique
  let cntChar = 0;
  
  // Traverse the String
  for (let i = 0; i < N; i++)
  {
    // Update frequency of str[i]
    if(mp.has(str[i]))
    {
      mp.set(str[i],
      mp.get(str[i]) + 1);
    }
    else
    {
      mp.set(str[i], 1);
    }
  }
  
  // Traverse the map
  for (let [key, value] of mp.entries())
  {
    // Insert current
    // frequency into pq
    pq.push(value);
  }
       
 pq.sort(function(a,b){return b-a;});
     
  // Traverse the priority_queue
  while (pq.length!=0)
  {
    // Stores topmost
    // element of pq
    let frequent = pq[0];
  
    // Pop the topmost element
    pq.shift();
  
    // If pq is empty
    if (pq.length==0) {
  
      // Return cntChar
      return cntChar;
    }
  
    // If frequent and topmost
    // element of pq are equal
    if (frequent == pq[0])
    {
      // If frequency of the topmost
      // element is greater than 1
      if (frequent > 1)
      {
        // Insert the decremented
        // value of frequent
        pq.push(frequent - 1);
        pq.sort(function(a,b){return b-a;});
      }
  
      // Update cntChar
      cntChar++;
    }
  }
  
  return cntChar;
}
 
// Driver Code
let str = "abbbcccd";
let N = str.length;
document.write(minCntCharDeletionsfrequency(
         str.split(""), N));
 
 
// This code is contributed by unknown2108
</script>

Producción

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

Enfoque 2: Disminuir cada duplicado hasta que sea único

Primero comenzaremos calculando la frecuencia de cada carácter. Luego, en este enfoque, iteramos sobre las frecuencias, y para cada frecuencia, verificaremos si esta frecuencia ya se ha visto. Si es así, disminuiremos la frecuencia hasta que sea única o cero (lo que significa que hemos eliminado todas las apariciones de este carácter).

Almacene la frecuencia de cada carácter en la string dada s en una array de frecuencia llamada fre (de tamaño 26 para cada carácter). Almacenamos la frecuencia de cada carácter c en el índice c-‘a’ .
inicialice el cnt a 0 , que almacena el recuento de caracteres que deben eliminarse. Además, inicializamos un HashSet visto que almacena las frecuencias que hemos ocupado.
Iterar sobre los caracteres de la a a la z como 0 a 25 , para cada carácter:
1. seguir disminuyendo la frecuencia del carácter hasta que no esté presente en la vista e incrementar el cnt cada vez que disminuyamos la frecuencia.
2. cuando la frecuencia se vuelva única (o cero) insértela en el conjunto visto.

C++

#include <bits/stdc++.h>
using namespace std;
 
int minDeletions(string s)
{
    // initializing "fre" vector to get count of frequency
    // of each character
    vector<int> fre(26, 0);
    set<int> seen; // initialize a seen hashset to store
                   // occupied frequencies
    int cnt = 0;
 
    for (int i = 0; i < s.length(); i++) {
        fre[s[i] - 'a']++;
    }
 
    for (int i = 0; i < 26; i++) {
 
        // if fre[i] is already present in seen set, we
        // decrement fre[i] and increment cnt;
        while (fre[i] && seen.find(fre[i]) != seen.end()) {
            fre[i]--;
            cnt++;
        }
 
        seen.insert(
            fre[i]); // when frequency of characters become
                     // unique insert it into seen set.
    }
 
    return cnt;
}
int main()
{
    string s = "aaabbbcc";
    cout << minDeletions(s) << endl;
    s = "aab";
    cout << minDeletions(s) << endl;
 
    return 0;
}

Java

// Java program to implement
// the above approach
import java.util.*;
class GFG{
 
// Function to find the minimum count of
// characters required to be deleted to make
// frequencies of all characters unique
static int minCntCharDeletionsfrequency(char[] str,
                                        int N)
{
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int count = 0;
         
        // get the frequencies of each letter in the string
        for(char c: str){
            if(!map.containsKey(c)){
                map.put(c, 1);
            }else{
                map.put(c, map.get(c) + 1);
            }
        }
        // store the frequencies into an arraylist
        ArrayList<Integer> frequencies = new ArrayList<>(map.values());
         
        // initialize hashset
        HashSet<Integer> set = new HashSet<Integer>();
        for(int value: frequencies){
            if(!set.contains(value)){
                set.add(value);
            }else{
                while(value > 0 && set.contains(value)){
                    value--;
                    count++;
                }
                set.add(value);
            }
        }
        return count;
    }
 
// Driver Code
public static void main(String[] args)
{
String str = "abbbcccd";
 
// Stores length of str
int N = str.length();
System.out.print(minCntCharDeletionsfrequency(
        str.toCharArray(), N));
}
}
 
// This code is contributed by Rajput-Ji

Producción

2
0

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

Publicación traducida automáticamente

Artículo escrito por saikumarkudikala y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Java

Python3

C#

Javascript

C++

Java

Deja una respuesta Cancelar la respuesta