Suma y producto de frecuencias principales de caracteres en una string

Dada una string str que contiene solo alfabetos ingleses en minúsculas, la tarea es encontrar la suma y el producto de todas las frecuencias principales de los caracteres en str .
Ejemplos: 
 

Entrada: str = «geeksforgeeks» 
Salida: 6, 8 
Solo los caracteres ‘g’, ‘k’ y ‘s’ tienen frecuencias principales, es decir, 2 + 2 + 2 = 6 y 2 * 2 * 2 = 8 
 

Personaje	frecuencia
gramo	2
mi	4
k	2
s	2
F	1
o	1
r	1

Entrada: str = “algoritmos” 
Salida: 0, 0 
 

Acercarse: 
 

• Recorra la string y almacene las frecuencias de todos los caracteres en una tabla hash.
• Encuentre las frecuencias que son primos usando la criba de Eratóstenes .
• Calcule la suma y el producto de todas estas frecuencias principales y finalmente imprima la suma y el producto.

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

// C++ program to find Sum and product of Prime
// Frequencies of Characters in a String
#include <bits/stdc++.h>
using namespace std;
 
// Function to create Sieve to check primes
void SieveOfEratosthenes(bool prime[], int p_size)
{
    // false here indicates
    // that it is not prime
    prime[0] = false;
    prime[1] = false;
 
    for (int p = 2; p * p <= p_size; p++) {
 
        // If prime[p] is not changed,
        // then it is a prime
        if (prime[p]) {
 
            // Update all multiples of p,
            // set them to non-prime
            for (int i = p * 2; i <= p_size; i += p)
                prime[i] = false;
        }
    }
}
 
// Function to find the sum of prime frequencies
// of the characters of the given string
void sumProdOfPrimeFreq(string s)
{
    bool prime[s.length() + 1];
    memset(prime, true, sizeof(prime));
 
    SieveOfEratosthenes(prime, s.length() + 1);
 
    int i, j;
 
    // map is used to store
    // character frequencies
    unordered_map<char, int> m;
    for (i = 0; i < s.length(); i++)
        m[s[i]]++;
 
    int sum = 0, product = 1;
 
    // Traverse the map
    for (auto it = m.begin(); it != m.end(); it++) {
 
        // If the frequency is prime
        if (prime[it->second]) {
            sum += it->second;
            product *= it->second;
        }
    }
 
    cout << "Sum = " << sum;
    cout << "\nProduct = " << product;
}
 
// Driver code
int main()
{
    string s = "geeksforgeeks";
 
    sumProdOfPrimeFreq(s);
    return 0;
}

// Java program to find Sum and product of Prime
// Frequencies of Characters in a String
import java.util.*;
 
class GFG
{
 
    // Function to create Sieve to check primes
    static void SieveOfEratosthenes(boolean prime[],
                                        int p_size)
    {
        // false here indicates
        // that it is not prime
        prime[0] = false;
        prime[1] = false;
 
        for (int p = 2; p * p <= p_size; p++)
        {
 
            // If prime[p] is not changed,
            // then it is a prime
            if (prime[p])
            {
 
                // Update all multiples of p,
                // set them to non-prime
                for (int i = p * 2; i < p_size; i += p)
                {
                    prime[i] = false;
                }
            }
        }
    }
 
    // Function to find the sum of prime frequencies
    // of the characters of the given string
    static void sumProdOfPrimeFreq(char[] s)
    {
        boolean[] prime = new boolean[s.length + 1];
        Arrays.fill(prime, true);
 
        SieveOfEratosthenes(prime, s.length + 1);
 
        int i, j;
 
        // map is used to store
        // character frequencies
        Map<Character, Integer> mp = new HashMap<>();
        for (i = 0; i < s.length; i++)
        {
            mp.put(s[i], mp.get(s[i]) == null ? 1 : mp.get(s[i]) + 1);
        }
 
        int sum = 0, product = 1;
 
        // Traverse the map
        for (Map.Entry<Character, Integer> it : mp.entrySet())
        {
 
            // If the frequency is prime
            if (prime[it.getValue()])
            {
                sum += it.getValue();
                product *= it.getValue();
            }
        }
 
        System.out.print("Sum = " + sum);
        System.out.println("\nProduct = " + product);
    }
 
    // Driver code
    public static void main(String[] args)
    {
        String s = "geeksforgeeks";
 
        sumProdOfPrimeFreq(s.toCharArray());
    }
}
 
// This code is contributed by 29AjayKumar

# Python3 program to find Sum and product of Prime
# Frequencies of Characters in a String
 
# Function to create Sieve to check primes
def SieveofEratosthenes(prime, p_size):
 
    # false here indicates
    # that it is not prime
    prime[0] = False
    prime[1] = False
 
    for p in range(2, p_size + 1):
 
        # If prime[p] is not changed,
        # then it is a prime
        if prime[p]:
 
            # Update all multiples of p,
            # set them to non-prime
            for i in range(p * 2, p_size + 1, p):
                prime[i] = False
 
# Function to find the sum of prime frequencies
# of the characters of the given string
def sumProdOfPrimeFreq(s):
    prime = [True] * (len(s) + 2)
 
    SieveofEratosthenes(prime, len(s) + 1)
 
    i = 0
    j = 0
 
    # map is used to store
    # character frequencies
    m = dict()
 
    for i in range(len(s)):
        m[s[i]] = (m[s[i]] + 1) if s[i] in m else 1
 
    s = 0
    product = 1
 
    # Traverse the map
    for it in m:
 
        # If the frequency is prime
        if prime[m[it]]:
            s += m[it]
            product *= m[it]
 
    print("Sum =", s)
    print("Product =", product)
 
# Driver code
if __name__ == "__main__":
    s = "geeksforgeeks"
    sumProdOfPrimeFreq(s)
 
# This code is contributed by
# sanjeev2552

// C# program to find Sum and product of Prime
// Frequencies of Characters in a String
using System;
using System.Collections.Generic;
 
class GFG
{
 
    // Function to create Sieve to check primes
    static void SieveOfEratosthenes(bool []prime,
                                        int p_size)
    {
        // false here indicates
        // that it is not prime
        prime[0] = false;
        prime[1] = false;
 
        for (int p = 2; p * p <= p_size; p++)
        {
 
            // If prime[p] is not changed,
            // then it is a prime
            if (prime[p])
            {
 
                // Update all multiples of p,
                // set them to non-prime
                for (int i = p * 2; i < p_size; i += p)
                {
                    prime[i] = false;
                }
            }
        }
    }
 
    // Function to find the sum of prime frequencies
    // of the characters of the given string
    static void sumProdOfPrimeFreq(char[] s)
    {
        int i;
        bool[] prime = new bool[s.Length + 1];
        for(i=0;i<s.Length + 1;i++){
            prime[i]=true;
        }
 
        SieveOfEratosthenes(prime, s.Length + 1);
 
         
 
        // map is used to store
        // character frequencies
        Dictionary<char, int> mp = new Dictionary<char, int>();
        for (i = 0 ; i < s.Length; i++)
        {
            if(mp.ContainsKey(s[i]))
            {
                var val = mp[s[i]];
                mp.Remove(s[i]);
                mp.Add(s[i], val + 1);
            }
            else
            {
                mp.Add(s[i], 1);
            }
        }
 
        int sum = 0, product = 1;
 
        // Traverse the map
        foreach(KeyValuePair<char, int> it in mp)
        {
 
            // If the frequency is prime
            if (prime[it.Value])
            {
                sum += it.Value;
                product *= it.Value;
            }
        }
 
        Console.Write("Sum = " + sum);
        Console.WriteLine("\nProduct = " + product);
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        String s = "geeksforgeeks";
 
        sumProdOfPrimeFreq(s.ToCharArray());
    }
}
 
// This code is contributed by Princi Singh

<script>
// Javascript program to find Sum and product of Prime
// Frequencies of Characters in a String
 
// Function to create Sieve to check primes
function SieveOfEratosthenes(prime, p_size) {
    // false here indicates
    // that it is not prime
    prime[0] = false;
    prime[1] = false;
 
    for (let p = 2; p * p <= p_size; p++) {
 
        // If prime[p] is not changed,
        // then it is a prime
        if (prime[p]) {
 
            // Update all multiples of p,
            // set them to non-prime
            for (let i = p * 2; i <= p_size; i += p)
                prime[i] = false;
        }
    }
}
 
// Function to find the sum of prime frequencies
// of the characters of the given string
function sumProdOfPrimeFreq(s) {
    let prime = new Array(s.length + 1);
    prime.fill(true);
 
    SieveOfEratosthenes(prime, s.length + 1);
 
    let i, j;
 
    // map is used to store
    // character frequencies
    let m = new Map();
    for (i = 0; i < s.length; i++)
        m.set(s[i], m.get(s[i]) == null ? 1 : m.get(s[i]) + 1);
 
    let sum = 0, product = 1;
 
    // Traverse the map
    for (let it of m) {
        console.log(m)
        // If the frequency is prime
        if (prime[it[1]]) {
            sum += it[1];
            product *= it[1];
        }
    }
 
    document.write("Sum = " + sum);
    document.write("<br>Product = " + product);
}
 
// Driver code
 
let s = "geeksforgeeks";
 
sumProdOfPrimeFreq(s);
 
// This code is contributed by gfgking
</script>

Sum = 6
Product = 8

Complejidad de tiempo: O(N*log(logN)), donde N es la longitud de la string dada.

Espacio Auxiliar: O(N), ya que se ha tomado N espacio extra.