Eliminar caracteres que aparecen más de k veces

Dada una string de letras minúsculas, redúzcala eliminando los caracteres que aparecen más de k veces en la string.
Ejemplos: 

Input : str = "geeksforgeeks"
        k = 2
Output : for

Input : str = "geeksforgeeks"
        k = 3
Output : gksforgks

Acercarse :  

• Cree una tabla hash de 26 índices, donde el índice 0 representa ‘a’ y el índice 1 representa ‘b’ y así sucesivamente. Inicialice la tabla hash a cero.
• Iterar a través de la string y contar incrementar la frecuencia del carácter str[i] en la tabla hash.
• Ahora, una vez más, recorra la string y agregue aquellos caracteres en la nueva string cuya frecuencia en la tabla hash sea menor que k y omita aquellos que parezcan más que iguales a k.

Complejidad de tiempo – O(N)
A continuación se muestra la implementación del enfoque anterior: 

// C++ program to reduce the string by
// removing the characters which
// appears more than k times
#include <bits/stdc++.h>
using namespace std;
 
const int MAX_CHAR = 26;
 
void removeChars(char arr[], int k)
{
    // Hash table initialised to 0
    int hash[MAX_CHAR] = { 0 };
 
    // Increment the frequency of the character
    int n = strlen(arr);
    for (int i = 0; i < n; ++i)
        hash[arr[i] - 'a']++;   
 
    // Next index in reduced string
    int index = 0;
    for (int i = 0; i < n; ++i) {
 
        // Append the characters which
        // appears less than k times
        if (hash[arr[i] - 'a'] < k) {
           arr[index++] = arr[i];
        }
    }
 
    arr[index] = '\0';
}
 
int main()
{
    char str[] = "geeksforgeeks";
    int k = 2;
    removeChars(str, k);
    cout << str;
    return 0;
}

// Java program to reduce the string by
// removing the characters which
// appears more than k times
import java.util.*;
class Solution
{
  
static final int MAX_CHAR = 26;
  
static void removeChars(char arr[], int k)
{
    // Hash table initialised to 0
    int hash[]=new int[MAX_CHAR];
     
    for (int i = 0; i <MAX_CHAR; ++i)
    hash[i]=0;
  
    // Increment the frequency of the character
    int n = (arr).length;
    for (int i = 0; i < n; ++i)
        hash[arr[i] - 'a']++;   
  
    // Next index in reduced string
    int index = 0;
    for (int i = 0; i < n; ++i) {
  
        // Append the characters which
        // appears less than k times
        if (hash[arr[i] - 'a'] < k) {
           arr[index++] = arr[i];
        }
    }
    for (int i = index; i < n; ++i)
    arr[i] = ' ';
}
  
public static void main(String args[])
{
    char str[] = "geeksforgeeks".toCharArray();;
    int k = 2;
    removeChars(str, k);
    System.out.println(String.valueOf( str));
}
 
}
//contributed by Arnab Kundu

# Python 3 program to reduce the string by
# removing the characters which
# appears more than k times
MAX_CHAR = 26
 
def removeChars(arr, k):
     
    # Hash table initialised to 0
    hash = [0 for i in range(MAX_CHAR)]
 
    # Increment the frequency of the character
    n = len(arr)
    for i in range(n):
        hash[ord(arr[i]) - ord('a')] += 1
 
    # Next index in reduced string
    index = 0
    for i in range(n):
         
        # Append the characters which
        # appears less than k times
        if (hash[ord(arr[i]) - ord('a')] < k):
            arr[index] = arr[i]
            index += 1
         
    arr[index] = ' '
     
    for i in range(index):
        print(arr[i], end = '')
 
# Driver code
if __name__ == '__main__':
    str = "geeksforgeeks"
    str = list(str)
    k = 2
    removeChars(str, k)
 
# This code is contributed by
# Shashank_Sharma

// C# program to reduce the string by
// removing the characters which
// appears more than k times
using System;
public class Solution{
 
    static readonly int MAX_CHAR = 26;
 
    static void removeChars(char []arr, int k)
    {
        // Hash table initialised to 0
        int []hash=new int[MAX_CHAR];
 
        for (int i = 0; i <MAX_CHAR; ++i)
        hash[i]=0;
 
        // Increment the frequency of the character
        int n = (arr).Length;
        for (int i = 0; i < n; ++i)
            hash[arr[i] - 'a']++;    
 
        // Next index in reduced string
        int index = 0;
        for (int i = 0; i < n; ++i) {
 
            // Append the characters which
            // appears less than k times
            if (hash[arr[i] - 'a'] < k) {
            arr[index++] = arr[i];
            }
        }
        for (int i = index; i < n; ++i)
        arr[i] = ' ';
    }
 
    public static void Main()
    {
        char []str = "geeksforgeeks".ToCharArray();;
        int k = 2;
        removeChars(str, k);
        Console.Write(String.Join("",str));
    }
 
}
// This code is contributed by PrinciRaj1992

<?php
// PHP program to reduce the string by
// removing the characters which
// appears more than k times
$MAX_CHAR = 26;
 
function removeChars($arr, $k)
{
    global $MAX_CHAR;
     
    // Hash table initialised to 0
    $hash = array_fill(0, $MAX_CHAR, NULL);
 
    // Increment the frequency of
    // the character
    $n = strlen($arr);
    for ($i = 0; $i < $n; ++$i)
        $hash[ord($arr[$i]) - ord('a')]++;
 
    // Next index in reduced string
    $index = 0;
    for ($i = 0; $i < $n; ++$i)
    {
 
        // Append the characters which
        // appears less than k times
        if ($hash[ord($arr[$i]) - ord('a')] < $k)
        {
            $arr[$index++] = $arr[$i];
        }
    }
     
    $arr[$index] = '';
    for($i = 0; $i < $index; $i++)
        echo $arr[$i];
}
 
// Driver Code
$str = "geeksforgeeks";
$k = 2;
removeChars($str, $k);
 
// This code is contributed by ita_c
?>

<script>
 
// JavaScript program to reduce the string by
// removing the characters which
// appears less than k times
     
    let  MAX_CHAR = 26;
     
    // Function to reduce the string by
// removing the characters which
// appears less than k times
    function removeChars(str,k)
    {
        // Hash table initialised to 0
        let hash = new Array(MAX_CHAR);
         for(let i=0;i<hash.length;i++)
        {
            hash[i]=0;
        }
        // Increment the frequency of the character
        let n = str.length;
        for (let i = 0; i < n; ++i) {
            hash[str[i].charCodeAt(0) -
            'a'.charCodeAt(0)]++;
        }
  
        // create a new empty string
        let index = "";
        for (let i = 0; i < n; ++i) {
  
            // Append the characters which
            // appears more than equal to k times
            if (hash[str[i].charCodeAt(0) -
            'a'.charCodeAt(0)] < k)
            {
                index += str[i];
            }
        }
  
        return index;
    }
     
    // Driver Code
    let str = "geeksforgeeks";
    let k = 2;
    document.write(removeChars(str, k));
     
 
// This code is contributed by rag2127
 
</script>

for

Complejidad de tiempo: O(n), donde n representa el tamaño de la array dada.

Espacio auxiliar: O(26), no se requiere espacio adicional, por lo que es una constante.

Método n.º 2: uso de las funciones integradas de Python:

• Escanearemos la string y contaremos la ocurrencia de todos los caracteres usando la función Counter() incorporada.
• Ahora, una vez más, recorra la string y agregue aquellos caracteres en la nueva string cuya frecuencia en el diccionario de frecuencias sea menor que k y omita aquellos que parezcan más que iguales a k.

Nota: Este método es aplicable para todo tipo de caracteres.

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

# Python 3 program to reduce the string
# by removing the characters which
# appears more than k times
from collections import Counter
 
# Function to reduce the string by
# removing the characters which
# appears more than k times
def removeChars(str, k):
   
    # Using Counter function to
    # count frequencies
    freq = Counter(str)
     
    # create a new empty string
    res = ""
 
    for i in range(len(str)):
 
        # Append the characters which
        # appears less than equal to k times
        if (freq[str[i]] < k):
            res += str[i]
 
    return res
 
 
# Driver Code
if __name__ == "__main__":
 
    str = "geeksforgeeks"
    k = 2
 
    print(removeChars(str, k))
 
# This code is contributed by vikkycirus

Producción:

for

Complejidad de tiempo: O(n), donde n representa el tamaño de la array dada.

Espacio auxiliar: O(26), no se requiere espacio adicional, por lo que es una constante.