Given a string str containing only lowercase characters. The task is to print the characters having prime frequency in the order of their occurrence.
Note that repeated elements with prime frequencies are printed as many times as they occur in order of their occurrence.
Examples:
Input: str = “neveropen”
Output: gksgks
Character Frequency ‘g’ 2 ‘e’ 4 ‘k’ 2 ‘s’ 2 ‘f’ 1 ‘o’ 1 ‘r’ 1 ‘g’, ‘k’ and ‘s’ are the only characters with prime frequencies.
Input: str = “aeroplane”
Output: aeae
Approach: Create a frequency array to store the frequency of each of the character of the given string str. Traverse the string str again and check whether the frequency of that character is prime using Sieve Of Eratosthenes.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define SIZE 26// Function to create Sieve to check primesvoid 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 print the prime frequency characters// in the order of their occurrencevoid printChar(string str, int n){ bool prime[n + 1]; memset(prime, true, sizeof(prime)); // Function to create Sieve to check primes SieveOfEratosthenes(prime, str.length() + 1); // To store the frequency of each of // the character of the string int freq[SIZE]; // Initialize all elements of freq[] to 0 memset(freq, 0, sizeof(freq)); // Update the frequency of each character for (int i = 0; i < n; i++) freq[str[i] - 'a']++; // Traverse str character by character for (int i = 0; i < n; i++) { // If frequency of current character is prime if (prime[freq[str[i] - 'a']]) { cout << str[i]; } }}// Driver codeint main(){ string str = "neveropen"; int n = str.length(); printChar(str, n); return 0;} |
Java
// Java implementation of the approachclass GFG{ static int SIZE = 26;// Function to create Sieve to check primesstatic 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 print the prime frequency characters// in the order of their occurrencestatic void printChar(String str, int n){ boolean []prime = new boolean[n + 1]; for(int i = 0; i < n + 1; i++) prime[i] = true; // Function to create Sieve to check primes SieveOfEratosthenes(prime, str.length() + 1); // To store the frequency of each of // the character of the string int []freq = new int[SIZE]; // Initialize all elements of freq[] to 0 for(int i =0; i< SIZE; i++) freq[i]=0; // Update the frequency of each character for (int i = 0; i < n; i++) freq[str.charAt(i) - 'a']++; // Traverse str character by character for (int i = 0; i < n; i++) { // If frequency of current character is prime if (prime[freq[str.charAt(i) - 'a']]) { System.out.print(str.charAt(i)); } }}// Driver codepublic static void main(String[] args) { String str = "neveropen"; int n = str.length(); printChar(str, n);}} // This code is contributed by PrinciRaj1992 |
Python3
# Python 3 implementation of the approachSIZE = 26from math import sqrt# Function to create Sieve to check primesdef SieveOfEratosthenes(prime, p_size): # false here indicates # that it is not prime prime[0] = False prime[1] = False for p in range(2, int(sqrt(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, p): prime[i] = False# Function to print the prime frequency characters# in the order of their occurrencedef printChar(str, n): prime = [True for i in range(n + 1)] # Function to create Sieve to check primes SieveOfEratosthenes(prime, len(str) + 1) # To store the frequency of each of # the character of the string freq = [0 for i in range(SIZE)] # Update the frequency of each character for i in range(n): freq[ord(str[i]) - ord('a')] += 1 # Traverse str character by character for i in range(n): # If frequency of current character is prime if (prime[freq[ord(str[i]) - ord('a')]]): print(str[i], end = "")# Driver codeif __name__ == '__main__': str = "neveropen" n = len(str) printChar(str, n) # This code is contributed by Surendra_Gangwar |
C#
// C# implementation of the approach using System;class GFG{ static int SIZE = 26; // 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 print the prime frequency characters // in the order of their occurrence static void printChar(string str, int n) { bool[] prime = new bool[n + 1]; for (int i = 0; i < n + 1; i++) prime[i] = true; // Function to create Sieve to check primes SieveOfEratosthenes(prime, str.Length + 1); // To store the frequency of each of // the character of the string int[] freq = new int[SIZE]; // Initialize all elements of freq[] to 0 for (int i = 0; i < SIZE; i++) freq[i] = 0; // Update the frequency of each character for (int i = 0; i < n; i++) freq[str[i] - 'a']++; // Traverse str character by character for (int i = 0; i < n; i++) { // If frequency of current character is prime if (prime[freq[str[i] - 'a']]) { Console.Write(str[i]); } } } // Driver code public static void Main(String[] args) { String str = "neveropen"; int n = str.Length; printChar(str, n); }}// This code is contributed by// sanjeev2552 |
Javascript
<script>// javaScript implementation of the approachlet SIZE = 26;// Function to create Sieve to check primes// Function to create Sieve to check primesfunction 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; } } return prime;}// Function to print the prime frequency characters// in the order of their occurrencefunction printChar(str, n){ let prime = []; for(let i = 0; i<n+1; i++){ prime.push(true); } // Function to create Sieve to check primes prime = SieveOfEratosthenes(prime, str.length + 1); // To store the frequency of each of // the character of the string let freq = []; for(let i = 0; i<26; i++){ freq.push(0); } // Update the frequency of each character for (let i = 0; i < n; i++) freq[str.charCodeAt(i) - 97]++; // Traverse str character by character for (let i = 0; i < n; i++) { // If frequency of current character is prime if (prime[freq[str.charCodeAt(i) - 97]]) { document.write(str[i]); } }}// Driver codelet str = "neveropen";let n = str.length;printChar(str, n);</script> |
Output
gksgks
Time Complexity: O(n)
Auxiliary Space: O(n)
Method #2: Using built-in functions:
Approach:
We will scan the string and count the occurrence of all characters using built-in Counter() function after that we traverse the string and check if the occurrences are prime or not if there is any prime frequency then we print it.
Note: This method is applicable for all type of characters
Below is the implementation of the above approach:
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// Function to check primesbool prime(int n){ if (n <= 1) return false; int max_div = floor(sqrt(n)); for (int i = 2; i < 1 + max_div; i++) { if (n % i == 0) return false; } return true;}void checkString(string s){ // Counting the frequency of all // character using Counter function unordered_map<char, int> freq; for (int i = 0; i < s.size(); i++) { freq[s[i]]++; } // Traversing string for (int i = 0; i < s.size(); i++) { if (prime(freq[s[i]])) cout << s[i]; }}// Driver codeint main(){ string s = "neveropen"; // Passing string to checkString function checkString(s);}// This code is contributed by Samim Hossain Mondal. |
Java
// Java code for the above approachimport java.io.*;import java.util.*;class GFG { // Function to check primesstatic boolean prime(int n){ if (n <= 1) return false; int max_div = (int)Math.floor(Math.sqrt(n)); for(int i = 2; i < 1 + max_div; i++) { if (n % i == 0) return false; } return true;} static void checkString(String s){ // Counting the frequency of all // character using Counter function Map<Character, Integer> freq = new HashMap<Character, Integer>(); for(int i = 0; i < s.length(); i++) { if (!freq.containsKey(s.charAt(i))) freq.put(s.charAt(i),0); freq.put(s.charAt(i),freq.get(s.charAt(i))+1); } // Traversing string for(int i = 0; i < s.length(); i++) { if (prime(freq.get(s.charAt(i)))) System.out.print(s.charAt(i)); }} // Driver code public static void main (String[] args) { String s = "neveropen"; // Passing string to checkString function checkString(s); }}// This code is contributed by avanitrachhadiya2155 |
Python3
# Python code for the above approach# importing Counter functionfrom collections import Counterimport math# Function to check primesdef prime(n): if n <= 1: return False max_div = math.floor(math.sqrt(n)) for i in range(2, 1 + max_div): if n % i == 0: return False return Truedef checkString(s): # Counting the frequency of all # character using Counter function freq = Counter(s) # Traversing string for i in range(len(s)): if prime(freq[s[i]]): print(s[i], end="")# Driver codes = "neveropen"# passing string to checkString functioncheckString(s)# This code is contributed by vikkycirus |
C#
// C# code for the above approachusing System;using System.Collections.Generic;class GFG{ // Function to check primesstatic bool prime(int n){ if (n <= 1) return false; int max_div = (int)Math.Floor(Math.Sqrt(n)); for(int i = 2; i < 1 + max_div; i++) { if (n % i == 0) return false; } return true;}static void checkString(string s){ // Counting the frequency of all // character using Counter function Dictionary<char, int> freq = new Dictionary<char, int>(); for(int i = 0; i < s.Length; i++) { if (!freq.ContainsKey(s[i])) freq[s[i]] = 0; freq[s[i]] += 1; } // Traversing string for(int i = 0; i < s.Length; i++) { if (prime(freq[s[i]])) Console.Write(s[i]); }}// Driver codepublic static void Main(){ string s = "neveropen"; // Passing string to checkString function checkString(s);}}// This code is contributed by ukasp |
Javascript
<script>// Javascript code for the above approach// Function to check primesfunction prime(n){ if (n <= 1) return false; let max_div = Math.floor(Math.sqrt(n)); for(let i = 2; i < 1 + max_div; i++) { if (n % i == 0) return false; } return true;}function checkString(s){ // Counting the frequency of all // character using Counter function let freq = new Map(); for(let i = 0; i < s.length; i++) { if (!freq.has(s[i])) freq.set(s[i], 0); freq.set(s[i], freq.get(s[i]) + 1); } // Traversing string for(let i = 0; i < s.length; i++) { if (prime(freq.get(s[i]))) document.write(s[i]); }}// Driver codelet s = "neveropen";// Passing string to checkString functioncheckString(s);// This code is contributed by rag2127</script> |
Output
gksgks
Time Complexity: O(n)
Auxiliary Space: O(26)
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!
