Given string str of length N, the task is to remove all the characters from the string whose frequencies are prime.
Examples:
Input: str = “neveropen”
Output: eeforee
Explanation:
The frequencies of characters is: { g=2, e=4, k=2, s=2, f=1, o=1, r=1}
So, g, k and s are the characters with prime frequencies so, they are removed from the string.
The resultant string is “eeforee”Input: str = “abcdef”
Output: abcdef
Explanation:
Since all the characters are unique with frequency as 1, so no character is removed.
Naive Approach: The simplest approach to solve this problem is to find the frequencies of every distinct character present in the string and for each character, check if its frequency is Prime or not. If the frequency is found to be prime, skip that character. Otherwise, append it to the new string formed.
Time Complexity: O( N 3/2)
Auxiliary Space: O(N)
Efficient Approach: The above approach can be optimized by using the Sieve of Eratosthenes to precompute Prime Numbers. Follow the steps below to solve the problem:
- Using Sieve of Eratosthenes, generate all prime numbers up to N and store them in the array prime[].
- Initialize a Map and store the frequency of each character.
- Then, traverse the string and find out which characters have prime frequencies with the help of the map and prime[] array.
- Ignore all those characters which have prime frequencies and store the rest in a new string.
- After the above steps, print the new string.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to perform the sieve of// eratosthenes algorithmvoid 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 stringvoid 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 Codeint main(){ string str = "neveropen"; // Function Call removePrimeFrequencies(str); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to perform the sieve of// eratosthenes algorithmstatic 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 Stringstatic 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 Codepublic static void main(String[] args){ String str = "neveropen"; // Function Call removePrimeFrequencies(str.toCharArray());}}// This code is contributed by aashish1995 |
Python3
# Python3 program for the above approach# Function to perform the sieve of# eratosthenes algorithmdef 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 Stringdef 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 = "neveropen" # Function CallremovePrimeFrequencies(list(Str))# This code is contributed by divyesh072019 |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to perform the sieve of// eratosthenes algorithmstatic 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 Stringstatic 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 Codepublic static void Main(String[] args){ String str = "neveropen"; // Function Call removePrimeFrequencies(str.ToCharArray());}}// This code is contributed by aashish1995 |
Javascript
<script>// JavaScript program for the above approach// Function to perform the sieve of// eratosthenes algorithmfunction 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 stringfunction 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 Codestr = "neveropen";// Function CallremovePrimeFrequencies(str);// This code is contributed by ukasp. </script> |
Output:
eeforee
Time Complexity: O(N*log (log N))
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
