Print all characters of string whose frequency is a power of K
Given string str of size N, the task is to print the characters of string whose frequency is a power of K in a lexicographically sorted order.
Examples:
Input: str = “aaacbb” K = 2
Output: bbc
Explanation: Frequency of a is 3 which is not the power of 2. Frequency of c is 1 and frequency of b is 2 which are the power of 2.Input: str = “BeginnergeekBeginner” K = 3
Output: eeeeeegggkkk
Naive Approach: The idea is to count frequency for every alphabet of the string, if the frequency is the power of K then add it to a new string. Sort the string and print it.
Time Complexity: O(N2)
Auxiliary Space: O(N)
Efficient Approach: The idea is to use Hashing. Below are the steps:
- Traverse the string and store the frequency of each alphabet in a Map
- Traverse the map and print the alphabets whose frequency is the power of K
Below is the implementation of the above approach:
C++
// C++ implementation for the above approach #include <bits/stdc++.h> using namespace std; // Function to count the frequency // of every alphabet in the string // and print the alphabets with // frequency as the power of K void countFrequency(string str, int N, int K) { // Map will store the frequency // of each alphabet of the string map< char , int > freq; // Store the frequency of each // alphabet of the string for ( int i = 0; i < N; i++) { freq[str[i]]++; } // Traverse the Map for ( auto i : freq) { // Calculate log of the // current string alphabet int lg = log2(i.second); // Power of 2 of the log value int a = pow (2, lg); if (a == i.second) { while (a--) cout << i.first << endl; } } } // Driver Code int main() { string str = "aaacbb" ; // Size of string int N = str.size(); // Initialize K int K = 2; // Function call countFrequency(str, N, K); return 0; } |
Java
// Java implementation for the above approach import java.util.*; class GFG{ // Function to count the frequency // of every alphabet in the String // and print the alphabets with // frequency as the power of K static void countFrequency(String str, int N, int K) { // Map will store the frequency // of each alphabet of the String HashMap<Character, Integer> freq = new HashMap<Character, Integer>(); // Store the frequency of each // alphabet of the String for ( int i = 0 ; i < N; i++) { if (freq.containsKey(str.charAt(i))) { freq.put(str.charAt(i), freq.get(str.charAt(i)) + 1 ); } else { freq.put(str.charAt(i), 1 ); } } // Traverse the Map for (Map.Entry<Character, Integer> i : freq.entrySet()) { // Calculate log of the // current String alphabet int lg = ( int )Math.ceil(Math.log(i.getValue())); // Power of 2 of the log value int a = ( int )Math.pow( 2 , lg); if (a == i.getValue()) { while (a--> 0 ) System.out.print(i.getKey() + "\n" ); } } } // Driver Code public static void main(String[] args) { String str = "aaacbb" ; // Size of String int N = str.length(); // Initialize K int K = 2 ; // Function call countFrequency(str, N, K); } } // This code is contributed by shikhasingrajput |
Python3
# Python code for the above approach import math # Function to count the frequency # of every alphabet in the string # and print the alphabets with # frequency as the power of K def countFrequency( str , N, K): # Map will store the frequency # of each alphabet of the string freq = {} # Store the frequency of each # alphabet of the string for i in range (N): if str [i] in freq.keys(): freq[ str [i]] = freq[ str [i]] + 1 else : freq[ str [i]] = 1 # Traverse the Map for i in sorted (freq.keys()): # Calculate log of the # current string alphabet lg = math.floor(math.log2(freq[i])) # Power of 2 of the log value a = math. pow ( 2 , lg) if a = = freq[i]: while a ! = 0 : print (i) a = a - 1 # Driver Code str = "aaacbb" # Size of string N = len ( str ) # Initialize K K = 2 # Function call countFrequency( str , N, K) # This code is contributed by Potta Lokesh |
C#
// C# code for the above approach using System; using System.Collections; using System.Collections.Generic; class GFG { // Function to count the frequency // of every alphabet in the String // and print the alphabets with // frequency as the power of K static void countFrequency( string str, int N, int K) { // Map will store the frequency // of each alphabet of the String Dictionary< char , int > freq = new Dictionary< char , int >(); // Store the frequency of each // alphabet of the String foreach ( char i in str) { if (freq.ContainsKey(i)) { freq[i]++; } else { freq[i]=1; } } ArrayList ch = new ArrayList(); // Traverse the dict foreach (KeyValuePair< char , int > i in freq) { // Calculate log of the // current String alphabet int lg = ( int )Math.Ceiling(Math.Log(i.Value)); // Power of 2 of the log value int a = ( int )Math.Pow(2, lg); if (a == i.Value) { while (a-->0) ch.Add(i.Key); } } ch.Sort(); for ( int i = 0; i < ch.Count; i++){ Console.Write(ch[i] + "\n" ); } } // Driver Code public static void Main () { string str = "aaacbb" ; // Size of String int N = str.Length; // Initialize K int K = 2; // Function call countFrequency(str, N, K); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // Javascript implementation for the above approach // Function to count the frequency // of every alphabet in the string // and print the alphabets with // frequency as the power of K function countFrequency(str, N, K) { // Map will store the frequency // of each alphabet of the string let freq = new Map(); // Store the frequency of each // alphabet of the string for (let i = 0; i < N; i++) { if (freq.has(str[i])) { freq.set(str[i], freq.get(str[i]) + 1) } else { freq.set(str[i], 1) } } let ch = []; // Traverse the Map for (i of freq) { // Calculate log of the // current string alphabet let lg = Math.floor(Math.log2(i[1])); // Power of 2 of the log value let a = Math.pow(2, lg); if (a == i[1]) { while (a--) ch.push(i[0]); } } ch.sort() ch.forEach((val) => { document.write(val + "<br>" ) }) } // Driver Code let str = "aaacbb" ; // Size of string let N = str.length; // Initialize K let K = 2; // Function call countFrequency(str, N, K); // This code is contributed by saurabh_jaiswal. </script> |
b b c
Time Complexity: O(N * log N)
Auxiliary Space: O(N)
Contact Us