Dada la string str de tamaño N , la tarea es imprimir los caracteres de la string cuya frecuencia es una potencia de K en un orden ordenado lexicográficamente.
Ejemplos:
Entrada: str = “aaacbb” K = 2
Salida: bbc
Explicación: La frecuencia de a es 3, que no es la potencia de 2. La frecuencia de c es 1 y la frecuencia de b es 2, que son la potencia de 2.Entrada: str = “geeksgeekgeeks” K = 3
Salida: eeeeeegggkkk
Enfoque ingenuo: la idea es contar la frecuencia para cada alfabeto de la string, si la frecuencia es la potencia de K , entonces agréguela a una nueva string. Ordene la string e imprímala.
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque Eficiente: La idea es usar Hashing . A continuación se muestran los pasos:
- Atraviese la string y almacene la frecuencia de cada alfabeto en un mapa
- Recorre el mapa e imprime los alfabetos cuya frecuencia es la potencia de K
A continuación se muestra la implementación del enfoque anterior:
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>
Producción
b b c
Complejidad de tiempo: O(N * log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por vansikasharma1329 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA