Eliminar caracteres de una string dada cuyas frecuencias son un número primo

Dada la string str de longitud N , la tarea es eliminar todos los caracteres de la string cuyas frecuencias son primos.

Ejemplos:

Entrada: str = “geeksforgeeks”
Salida: eeforee
Explicación:
La frecuencia de los caracteres es: { g=2, e=4, k=2, s=2, f=1, o=1, r=1}
Entonces, g , k y s son los caracteres con frecuencias primas, por lo que se eliminan de la string.
La string resultante es «eeforee»

Entrada: str = “abcdef”
Salida: abcdef 
Explicación:
Dado que todos los caracteres son únicos con una frecuencia de 1, no se elimina ningún carácter.

Enfoque ingenuo: el enfoque más simple para resolver este problema es encontrar las frecuencias de cada carácter distinto presente en la string y, para cada carácter, verificar si su frecuencia es principal o no. Si se encuentra que la frecuencia es principal, omita ese carácter. De lo contrario, agréguelo a la nueva string formada. 

Complejidad de Tiempo: O( N ^3/2 )
Espacio Auxiliar: O(N)

Enfoque eficiente: el enfoque anterior se puede optimizar mediante el uso de la criba de Eratóstenes para calcular previamente los números primos . Siga los pasos a continuación para resolver el problema:

• Usando Sieve of Eratosthenes , genere todos los números primos hasta N y guárdelos en la array prime[] .
• Inicialice un mapa y almacene la frecuencia de cada carácter .
• Luego, recorra la string y descubra qué caracteres tienen frecuencias principales con la ayuda del mapa y la array prime[].
• Ignore todos aquellos caracteres que tengan frecuencias principales y almacene el resto en una nueva string.
• Después de los pasos anteriores, imprima la nueva string.

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 perform the sieve of
// eratosthenes algorithm
void SieveOfEratosthenes(bool* prime, int n)
{
    // Initialize all entries in
    // prime[] as true
    for (int i = 0; i <= n; i++) {
        prime[i] = true;
    }
 
    // Initialize 0 and 1 as non prime
    prime[0] = prime[1] = false;
 
    // Traversing the prime array
    for (int i = 2; i * i <= n; i++) {
 
        // If i is prime
        if (prime[i] == true) {
 
            // All multiples of i must
            // be marked false as they
            // are non prime
            for (int j = 2; i * j <= n; j++) {
                prime[i * j] = false;
            }
        }
    }
}
 
// Function to remove characters which
// have prime frequency in the string
void removePrimeFrequencies(string s)
{
    // Length of the string
    int n = s.length();
 
    // Create a boolean array prime
    bool prime[n + 1];
 
    // Sieve of Eratosthenes
    SieveOfEratosthenes(prime, n);
 
    // Stores the frequency of character
    unordered_map<char, int> m;
 
    // Storing the frequencies
    for (int i = 0; i < s.length(); i++) {
        m[s[i]]++;
    }
 
    // New string that will be formed
    string new_string = "";
 
    // Removing the characters which
    // have prime frequencies
    for (int i = 0; i < s.length(); i++) {
 
        // If the character has
        // prime frequency then skip
        if (prime[m[s[i]]])
            continue;
 
        // Else concatenate the
        // character to the new string
        new_string += s[i];
    }
 
    // Print the modified string
    cout << new_string;
}
 
// Driver Code
int main()
{
    string str = "geeksforgeeks";
 
    // Function Call
    removePrimeFrequencies(str);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to perform the sieve of
// eratosthenes algorithm
static void SieveOfEratosthenes(boolean[] prime,
                                int n)
{
     
    // Initialize all entries in
    // prime[] as true
    for(int i = 0; i <= n; i++)
    {
        prime[i] = true;
    }
     
    // Initialize 0 and 1 as non prime
    prime[0] = prime[1] = false;
     
    // Traversing the prime array
    for(int i = 2; i * i <= n; i++)
    {
         
        // If i is prime
        if (prime[i] == true)
        {
             
            // All multiples of i must
            // be marked false as they
            // are non prime
            for(int j = 2; i * j <= n; j++)
            {
                prime[i * j] = false;
            }
        }
    }
}
 
// Function to remove characters which
// have prime frequency in the String
static void removePrimeFrequencies(char[] s)
{
     
    // Length of the String
    int n = s.length;
     
    // Create a boolean array prime
    boolean []prime = new boolean[n + 1];
     
    // Sieve of Eratosthenes
    SieveOfEratosthenes(prime, n);
 
    // Stores the frequency of character
    HashMap<Character, Integer> m = new HashMap<>();
     
    // Storing the frequencies
    for(int i = 0; i < s.length; i++)
    {
        if (m.containsKey(s[i]))
        {
            m.put(s[i], m.get(s[i]) + 1);
        }
        else
        {
            m.put(s[i], 1);
        }
    }
     
    // New String that will be formed
    String new_String = "";
     
    // Removing the characters which
    // have prime frequencies
    for(int i = 0; i < s.length; i++)
    {
         
        // If the character has
        // prime frequency then skip
        if (prime[m.get(s[i])])
            continue;
             
        // Else concatenate the
        // character to the new String
        new_String += s[i];
    }
     
    // Print the modified String
    System.out.print(new_String);
}
 
// Driver Code
public static void main(String[] args)
{
    String str = "geeksforgeeks";
     
    // Function Call
    removePrimeFrequencies(str.toCharArray());
}
}
 
// This code is contributed by aashish1995

# Python3 program for the above approach
 
# Function to perform the sieve of
# eratosthenes algorithm
def SieveOfEratosthenes(prime, n) :
      
    # Initialize all entries in
    # prime[] as true
    for i in range(n + 1) :   
        prime[i] = True
          
    # Initialize 0 and 1 as non prime
    prime[0] = prime[1] = False
      
    # Traversing the prime array
    i = 2
    while i*i <= n :
          
        # If i is prime
        if (prime[i] == True) :
              
            # All multiples of i must
            # be marked false as they
            # are non prime
            j = 2
            while i*j <= n :          
                prime[i * j] = False
                j += 1
        i += 1
         
# Function to remove characters which
# have prime frequency in the String
def removePrimeFrequencies(s) :
      
    # Length of the String
    n = len(s)
      
    # Create a bool array prime
    prime = [False] * (n + 1)
      
    # Sieve of Eratosthenes
    SieveOfEratosthenes(prime, n)
  
  
    # Stores the frequency of character
    m = {}
      
    # Storing the frequencies
    for i in range(len(s)) :   
        if s[i] in m :       
            m[s[i]]+= 1       
        else :      
            m[s[i]] = 1
      
    # New String that will be formed
    new_String = ""
      
    # Removing the characters which
    # have prime frequencies
    for i in range(len(s)) :
          
        # If the character has
        # prime frequency then skip
        if (prime[m[s[i]]]) :
            continue
              
        # Else concatenate the
        # character to the new String
        new_String += s[i]
      
    # Print the modified String
    print(new_String, end = "")
     
Str = "geeksforgeeks"
      
# Function Call
removePrimeFrequencies(list(Str))
 
# This code is contributed by divyesh072019

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to perform the sieve of
// eratosthenes algorithm
static void SieveOfEratosthenes(bool[] prime,
                                int n)
{
     
    // Initialize all entries in
    // prime[] as true
    for(int i = 0; i <= n; i++)
    {
        prime[i] = true;
    }
     
    // Initialize 0 and 1 as non prime
    prime[0] = prime[1] = false;
     
    // Traversing the prime array
    for(int i = 2; i * i <= n; i++)
    {
         
        // If i is prime
        if (prime[i] == true)
        {
             
            // All multiples of i must
            // be marked false as they
            // are non prime
            for(int j = 2; i * j <= n; j++)
            {
                prime[i * j] = false;
            }
        }
    }
}
 
// Function to remove characters which
// have prime frequency in the String
static void removePrimeFrequencies(char[] s)
{
     
    // Length of the String
    int n = s.Length;
     
    // Create a bool array prime
    bool []prime = new bool[n + 1];
     
    // Sieve of Eratosthenes
    SieveOfEratosthenes(prime, n);
 
    // Stores the frequency of character
    Dictionary<char,
               int> m = new Dictionary<char,
                                       int>();
     
    // Storing the frequencies
    for(int i = 0; i < s.Length; i++)
    {
        if (m.ContainsKey(s[i]))
        {
            m[s[i]]++;
        }
        else
        {
            m.Add(s[i], 1);
        }
    }
     
    // New String that will be formed
    String new_String = "";
     
    // Removing the characters which
    // have prime frequencies
    for(int i = 0; i < s.Length; i++)
    {
         
        // If the character has
        // prime frequency then skip
        if (prime[m[s[i]]])
            continue;
             
        // Else concatenate the
        // character to the new String
        new_String += s[i];
    }
     
    // Print the modified String
    Console.Write(new_String);
}
 
// Driver Code
public static void Main(String[] args)
{
    String str = "geeksforgeeks";
     
    // Function Call
    removePrimeFrequencies(str.ToCharArray());
}
}
 
// This code is contributed by aashish1995

<script>
 
 
// JavaScript program for the above approach
 
 
// Function to perform the sieve of
// eratosthenes algorithm
function SieveOfEratosthenes(prime, n)
{
    // Initialize all entries in
    // prime[] as true
    for (let i = 0; i <= n; i++) {
        prime[i] = true;
    }
 
    // Initialize 0 and 1 as non prime
    prime[0] = prime[1] = false;
 
    // Traversing the prime array
    for (let i = 2; i * i <= n; i++) {
 
        // If i is prime
        if (prime[i] == true) {
 
            // All multiples of i must
            // be marked false as they
            // are non prime
            for (let j = 2; i * j <= n; j++) {
                prime[i * j] = false;
            }
        }
    }
}
 
// Function to remove characters which
// have prime frequency in the string
function removePrimeFrequencies( s)
{
    // Length of the string
    var n = s.length;
 
    // Create a boolean array prime
    var prime = new Array(n + 1);
 
    // Sieve of Eratosthenes
    SieveOfEratosthenes(prime, n);
 
    // Stores the frequency of character
    var m = {};
    for(let i =0;i<s.length;i++)
      m[s[i]] = 0;
 
    // Storing the frequencies
    for (let i = 0; i < s.length; i++) {
        m[s[i]]++;
    }
   
    // New string that will be formed
    var new_string = "";
 
    // Removing the characters which
    // have prime frequencies
    for (let i = 0; i < s.length; i++) {
 
        // If the character has
        // prime frequency then skip
        if (prime[m[s[i]]])
            continue;
 
        // Else concatenate the
        // character to the new string
        new_string += s[i];
       
    }
 
    // Print the modified string
    console.log( new_string);
}
 
// Driver Code
str = "geeksforgeeks";
 
// Function Call
removePrimeFrequencies(str);
 
// This code is contributed by ukasp.   
 
</script>

eeforee

Complejidad de tiempo: O(N*log (log N))
Espacio auxiliar: O(N)