Número máximo de caracteres que no se repiten después de eliminar K caracteres

Dada una string S que contiene alfabetos ingleses en minúsculas de longitud N y un número entero K tal que K ≤ N . La tarea es encontrar el número máximo de caracteres que no se repiten después de eliminar K caracteres de la string.

Ejemplos:

Entrada: S = «geeksforgeeks», K = 3
Salida: 6
Explicación:
elimine 1 aparición de cada g, k y s para que la string final sea «geeksforee» y los 6 elementos distintos sean g, k, s, f, o y r

Entrada: S = «aabbccddeeffgghh», k = 1
Salida: 1
Explicación:
elimine 1 ocurrencia de cualquier carácter, tendremos solo un carácter que no se repetirá.

Enfoque ingenuo: la idea ingenua es eliminar todos los caracteres K posibles entre la string dada y luego encontrar los caracteres que no se repiten en toda la string formada. Imprime el máximo entre todos los recuentos de caracteres que no se repiten.
Complejidad de tiempo: O(N!), donde N es la longitud de la string dada.
Espacio Auxiliar: O(NK)

Enfoque eficiente: Para optimizar el enfoque anterior,  

La idea es eliminar K caracteres en orden creciente de frecuencia cuya frecuencia sea al menos 2 para obtener el recuento máximo de caracteres que no se repiten. 
 

A continuación se muestran los pasos: 

1. Cree una tabla hash para almacenar la frecuencia de cada elemento .
2. Inserta la frecuencia de cada elemento en un vector V y ordena el vector V en orden creciente .
3. Para cada elemento (por ejemplo, currentElement ) del vector V , encuentre el mínimo entre K y currentElement – ​​1 y disminuya tanto K como V[i] por el mínimo de los dos.
4. Repita el paso anterior hasta que K sea distinto de cero.
5. El conteo de 1s en el vector V da el número máximo de caracteres que no se repiten después de eliminar K caracteres.

 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 find maximum distinct
// character after removing K character
int maxDistinctChar(string s, int n, int k)
{
    // Freq implemented as hash table to
    // store frequency of each character
    unordered_map<int, int> freq;
 
    // Store frequency of each character
    for (int i = 0; i < n; i++)
        freq[s[i]]++;
 
    vector<int> v;
 
    // Insert each frequency in v
    for (auto it = freq.begin();
         it != freq.end(); it++) {
        v.push_back(it->second);
    }
 
    // Sort the freq of character in
    // non-decreasing order
    sort(v.begin(), v.end());
 
    // Traverse the vector
    for (int i = 0; i < v.size(); i++) {
        int mn = min(v[i] - 1, k);
 
        // Update v[i] and k
        v[i] -= mn;
        k -= mn;
    }
 
    // If K is still not 0
    if (k > 0) {
 
        for (int i = 0; i < v.size(); i++) {
            int mn = min(v[i], k);
            v[i] -= mn;
            k -= mn;
        }
    }
 
    // Store the final answer
    int res = 0;
    for (int i = 0; i < v.size(); i++)
 
        // Count this character if freq 1
        if (v[i] == 1)
            res++;
 
    // Return count of distinct characters
    return res;
}
 
// Driver Code
int main()
{
    // Given string
    string S = "geeksforgeeks";
 
    int N = S.size();
 
    // Given k
    int K = 1;
 
    // Function Call
    cout << maxDistinctChar(S, N, K);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
class GFG{
 
// Function to find maximum distinct
// character after removing K character
static int maxDistinctChar(char []s, int n, int k)
{
    // Freq implemented as hash table to
    // store frequency of each character
    HashMap<Integer,
            Integer> freq  = new HashMap<Integer,
                                         Integer>();
 
    // Store frequency of each character
    for (int i = 0; i < n; i++)
    {
        if(freq.containsKey((int)s[i]))
        {
            freq.put((int)s[i],
                     freq.get((int)s[i]) + 1);
        }
        else
        {
            freq.put((int)s[i], 1);
        }
    }
 
    Vector<Integer> v = new Vector<Integer>();
 
    // Insert each frequency in v
    for (Map.Entry<Integer, Integer> it : freq.entrySet())
    {
        v.add(it.getValue());
    }
 
    // Sort the freq of character in
    // non-decreasing order
    Collections.sort(v);
 
    // Traverse the vector
    for (int i = 0; i < v.size(); i++)
    {
        int mn = Math.min(v.get(i) - 1, k);
 
        // Update v[i] and k
        v.set(i, v.get(i) - mn);
        k -= mn;
    }
 
    // If K is still not 0
    if (k > 0)
    {
        for (int i = 0; i < v.size(); i++)
        {
            int mn = Math.min(v.get(i), k);
            v.set(i, v.get(i) - mn);
            k -= mn;
        }
    }
 
    // Store the final answer
    int res = 0;
    for (int i = 0; i < v.size(); i++)
 
        // Count this character if freq 1
        if (v.get(i) == 1)
            res++;
 
    // Return count of distinct characters
    return res;
}
 
// Driver Code
public static void main(String[] args)
{
    // Given String
    String S = "geeksforgeeks";
 
    int N = S.length();
 
    // Given k
    int K = 1;
 
    // Function Call
    System.out.print(maxDistinctChar(S.toCharArray(),
                                     N, K));
}
}
 
// This code is contributed by shikhasingrajput

# Python3 program for the above approach
from collections import defaultdict
 
# Function to find maximum distinct
# character after removing K character
def maxDistinctChar(s, n, k):
 
    # Freq implemented as hash table to
    # store frequency of each character
    freq = defaultdict (int)
 
    # Store frequency of each character
    for i in range (n):
        freq[s[i]] += 1
 
    v = []
 
    # Insert each frequency in v
    for it in freq.values():
        v.append(it)
 
    # Sort the freq of character in
    # non-decreasing order
    v.sort()
 
    # Traverse the vector
    for i in range (len(v)):
        mn = min(v[i] - 1, k)
 
        # Update v[i] and k
        v[i] -= mn
        k -= mn
 
    # If K is still not 0
    if (k > 0):
        for i in range (len(v)):
            mn = min(v[i], k);
            v[i] -= mn
            k -= mn
 
    # Store the final answer
    res = 0
    for i in range (len(v)):
 
        # Count this character if freq 1
        if (v[i] == 1):
            res += 1
 
    # Return count of distinct characters
    return res
 
# Driver Code
if __name__ == "__main__":
   
    # Given string
    S = "geeksforgeeks"
 
    N = len(S)
 
    # Given k
    K = 1
 
    # Function Call
    print(maxDistinctChar(S, N, K))
 
# This code is contributed by Chitranayal

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to find maximum distinct
// character after removing K character
static int maxDistinctChar(char []s, int n, int k)
{
     
    // Freq implemented as hash table to
    // store frequency of each character
    Dictionary<int,
               int> freq = new Dictionary<int,
                                          int>();
 
    // Store frequency of each character
    for(int i = 0; i < n; i++)
    {
        if(freq.ContainsKey((int)s[i]))
        {
            freq[(int)s[i]] = freq[(int)s[i]] + 1;
        }
        else
        {
            freq.Add((int)s[i], 1);
        }
    }
 
    List<int> v = new List<int>();
 
    // Insert each frequency in v
    foreach(KeyValuePair<int, int> it in freq)
    {
        v.Add(it.Value);
    }
 
    // Sort the freq of character in
    // non-decreasing order
    v.Sort();
 
    // Traverse the vector
    for(int i = 0; i < v.Count; i++)
    {
        int mn = Math.Min(v[i] - 1, k);
 
        // Update v[i] and k
        v[i] = v[i] - mn;
        k -= mn;
    }
 
    // If K is still not 0
    if (k > 0)
    {
        for(int i = 0; i < v.Count; i++)
        {
            int mn = Math.Min(v[i], k);
            v[i] = v[i] - mn;
            k -= mn;
        }
    }
 
    // Store the readonly answer
    int res = 0;
    for(int i = 0; i < v.Count; i++)
 
        // Count this character if freq 1
        if (v[i] == 1)
            res++;
 
    // Return count of distinct characters
    return res;
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given String
    String S = "geeksforgeeks";
 
    int N = S.Length;
 
    // Given k
    int K = 1;
 
    // Function call
    Console.Write(maxDistinctChar(S.ToCharArray(),
                                  N, K));
}
}
 
// This code is contributed by Amit Katiyar

<script>
 
// JavaScript program for the above approach
 
// Function to find maximum distinct
// character after removing K character
function maxDistinctChar(s, n, k)
{
    // Freq implemented as hash table to
    // store frequency of each character
    var freq = new Map();
 
    // Store frequency of each character
    for (var i = 0; i < n; i++)
    {
        if(freq.has(s[i]))
            freq.set(s[i], freq.get(s[i])+1)
        else   
            freq.set(s[i], 1)
    }
 
    var v = [];
 
    // Insert each frequency in v
    freq.forEach((value,key) => {
        
        v.push(value);
    });
 
    // Sort the freq of character in
    // non-decreasing order
    v.sort()
 
    // Traverse the vector
    for (var i = 0; i < v.length; i++) {
        var mn = Math.min(v[i] - 1, k);
 
        // Update v[i] and k
        v[i] -= mn;
        k -= mn;
    }
 
    // If K is still not 0
    if (k > 0) {
 
        for (var i = 0; i < v.length; i++) {
            var mn = Math.min(v[i], k);
            v[i] -= mn;
            k -= mn;
        }
    }
 
    // Store the final answer
    var res = 0;
    for (var i = 0; i < v.length; i++)
 
        // Count this character if freq 1
        if (v[i] == 1)
            res++;
 
    // Return count of distinct characters
    return res;
}
 
// Driver Code
 
// Given string
var S = "geeksforgeeks";
var N = S.length;
 
// Given k
var K = 1;
 
// Function Call
document.write( maxDistinctChar(S, N, K));
 
</script>

4

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