String dada str que contiene solo caracteres en minúsculas. El problema es imprimir los caracteres junto con su frecuencia en el orden en que aparecen y en el formato dado que se explica en los ejemplos a continuación.
Ejemplos:
Input : str = "geeksforgeeks" Output : g2 e4 k2 s2 f1 o1 r1 Input : str = "elephant" Output : e2 l1 p1 h1 a1 n1 t1
Fuente: Experiencia de entrevista de SAP | Conjunto 26
Enfoque: Cree una array de conteo para almacenar la frecuencia de cada carácter en la string dada str . Recorra la string str nuevamente y verifique si la frecuencia de ese carácter es 0 o no. Si no es 0, imprima el carácter junto con su frecuencia y actualice su frecuencia a 0 en la tabla hash. Esto se hace para que no se vuelva a imprimir el mismo carácter.
C++
// C++ implementation to print the character and // its frequency in order of its occurrence #include <bits/stdc++.h> using namespace std; #define SIZE 26 // function to print the character and its frequency // in order of its occurrence void printCharWithFreq(string str) { // size of the string 'str' int n = str.size(); // 'freq[]' implemented as hash table int freq[SIZE]; // initialize all elements of freq[] to 0 memset(freq, 0, sizeof(freq)); // accumulate frequency of each character in 'str' for (int i = 0; i < n; i++) freq[str[i] - 'a']++; // traverse 'str' from left to right for (int i = 0; i < n; i++) { // if frequency of character str[i] is not // equal to 0 if (freq[str[i] - 'a'] != 0) { // print the character along with its // frequency cout << str[i] << freq[str[i] - 'a'] << " "; // update frequency of str[i] to 0 so // that the same character is not printed // again freq[str[i] - 'a'] = 0; } } } // Driver program to test above int main() { string str = "geeksforgeeks"; printCharWithFreq(str); return 0; }
Java
// Java implementation to print the character and // its frequency in order of its occurrence public class Char_frequency { static final int SIZE = 26; // function to print the character and its // frequency in order of its occurrence static void printCharWithFreq(String str) { // size of the string 'str' int n = str.length(); // 'freq[]' implemented as hash table int[] freq = new int[SIZE]; // accumulate frequency of each character // in 'str' for (int i = 0; i < n; i++) freq[str.charAt(i) - 'a']++; // traverse 'str' from left to right for (int i = 0; i < n; i++) { // if frequency of character str.charAt(i) // is not equal to 0 if (freq[str.charAt(i) - 'a'] != 0) { // print the character along with its // frequency System.out.print(str.charAt(i)); System.out.print(freq[str.charAt(i) - 'a'] + " "); // update frequency of str.charAt(i) to // 0 so that the same character is not // printed again freq[str.charAt(i) - 'a'] = 0; } } } // Driver program to test above public static void main(String args[]) { String str = "geeksforgeeks"; printCharWithFreq(str); } } // This code is contributed by Sumit Ghosh
Python3
# Python3 implementation to pr the character and # its frequency in order of its occurrence # import library import numpy as np # Function to print the character and its # frequency in order of its occurrence def prCharWithFreq(str) : # Size of the 'str' n = len(str) # Initialize all elements of freq[] to 0 freq = np.zeros(26, dtype = np.int) # Accumulate frequency of each # character in 'str' for i in range(0, n) : freq[ord(str[i]) - ord('a')] += 1 # Traverse 'str' from left to right for i in range(0, n) : # if frequency of character str[i] # is not equal to 0 if (freq[ord(str[i])- ord('a')] != 0) : # print the character along # with its frequency print (str[i], freq[ord(str[i]) - ord('a')], end = " ") # Update frequency of str[i] to 0 so that # the same character is not printed again freq[ord(str[i]) - ord('a')] = 0 # Driver Code if __name__ == "__main__" : str = "geeksforgeeks"; prCharWithFreq(str); # This code is contributed by 'Saloni1297'
C#
// C# implementation to print the // character and its frequency in // order of its occurrence using System; class GFG { static int SIZE = 26; // function to print the character and its // frequency in order of its occurrence static void printCharWithFreq(String str) { // size of the string 'str' int n = str.Length; // 'freq[]' implemented as hash table int[] freq = new int[SIZE]; // accumulate frequency of each character // in 'str' for (int i = 0; i < n; i++) freq[str[i] - 'a']++; // traverse 'str' from left to right for (int i = 0; i < n; i++) { // if frequency of character str.charAt(i) // is not equal to 0 if (freq[str[i] - 'a'] != 0) { // print the character along with its // frequency Console.Write(str[i]); Console.Write(freq[str[i] - 'a'] + " "); // update frequency of str.charAt(i) to // 0 so that the same character is not // printed again freq[str[i] - 'a'] = 0; } } } // Driver program to test above public static void Main() { String str = "geeksforgeeks"; printCharWithFreq(str); } } // This code is contributed by Sam007
PHP
<?php // PHP implementation to print the // character and its frequency in // order of its occurrence $SIZE = 26; // function to print the character and // its frequency in order of its occurrence function printCharWithFreq($str) { global $SIZE; // size of the string 'str' $n = strlen($str); // 'freq[]' implemented as hash table $freq = array_fill(0, $SIZE, NULL); // accumulate frequency of each // character in 'str' for ($i = 0; $i < $n; $i++) $freq[ord($str[$i]) - ord('a')]++; // traverse 'str' from left to right for ($i = 0; $i < $n; $i++) { // if frequency of character str[i] // is not equal to 0 if ($freq[ord($str[$i]) - ord('a')] != 0) { // print the character along with // its frequency echo $str[$i] . $freq[ord($str[$i]) - ord('a')] . " "; // update frequency of str[i] to 0 // so that the same character is // not printed again $freq[ord($str[$i]) - ord('a')] = 0; } } } // Driver Code $str = "geeksforgeeks"; printCharWithFreq($str); // This code is contributed by ita_c ?>
Javascript
<script> // Javascript implementation to print the character and // its frequency in order of its occurrence let SIZE = 26; // function to print the character and its // frequency in order of its occurrence function printCharWithFreq(str) { // size of the string 'str' let n = str.length; // 'freq[]' implemented as hash table let freq = new Array(SIZE); for(let i = 0; i < freq.length; i++) { freq[i] = 0; } // accumulate frequency of each character // in 'str' for (let i = 0; i < n; i++) freq[str[i].charCodeAt(0) - 'a'.charCodeAt(0)]++; // traverse 'str' from left to right for (let i = 0; i < n; i++) { // if frequency of character str.charAt(i) // is not equal to 0 if (freq[str[i].charCodeAt(0) - 'a'.charCodeAt(0)] != 0) { // print the character along with its // frequency document.write(str[i]); document.write(freq[str[i].charCodeAt(0) - 'a'.charCodeAt(0)] + " "); // update frequency of str.charAt(i) to // 0 so that the same character is not // printed again freq[str[i].charCodeAt(0) - 'a'.charCodeAt(0)] = 0; } } } // Driver program to test above let str = "geeksforgeeks"; printCharWithFreq(str); // This code is contributed by rag2127. </script>
g2 e4 k2 s2 f1 o1 r1
Complejidad de tiempo: O(n), donde n es el número de caracteres de la string.
Espacio Auxiliar: O(1), ya que solo hay letras minúsculas.
Solución alternativa (usar hashing)
También podemos usar hash para resolver el problema.
C++
// C++ implementation to //print the characters and // frequencies in order // of its occurrence #include <bits/stdc++.h> using namespace std; void prCharWithFreq(string s) { // Store all characters and // their frequencies in dictionary unordered_map<char, int> d; for(char i : s) { d[i]++; } // Print characters and their // frequencies in same order // of their appearance for(char i : s) { // Print only if this // character is not printed // before if(d[i] != 0) { cout << i << d[i] << " "; d[i] = 0; } } } // Driver Code int main() { string s="geeksforgeeks"; prCharWithFreq(s); } // This code is contributed by rutvik_56
Java
// Java implementation to // print the characters and // frequencies in order // of its occurrence import java.util.*; class Gfg{ public static void prCharWithFreq(String s) { // Store all characters and // their frequencies in dictionary Map<Character, Integer> d = new HashMap<Character, Integer>(); for(int i = 0; i < s.length(); i++) { if(d.containsKey(s.charAt(i))) { d.put(s.charAt(i), d.get(s.charAt(i)) + 1); } else { d.put(s.charAt(i), 1); } } // Print characters and their // frequencies in same order // of their appearance for(int i = 0; i < s.length(); i++) { // Print only if this // character is not printed // before if(d.get(s.charAt(i)) != 0) { System.out.print(s.charAt(i)); System.out.print(d.get(s.charAt(i)) + " "); d.put(s.charAt(i), 0); } } } // Driver code public static void main(String []args) { String S = "geeksforgeeks"; prCharWithFreq(S); } } // This code is contributed by avanitrachhadiya2155
Python3
# Python3 implementation to print the characters and # frequencies in order of its occurrence def prCharWithFreq(str): # Store all characters and their frequencies # in dictionary d = {} for i in str: if i in d: d[i] += 1 else: d[i] = 1 # Print characters and their frequencies in # same order of their appearance for i in str: # Print only if this character is not printed # before. if d[i] != 0: print("{}{}".format(i,d[i]), end =" ") d[i] = 0 # Driver Code if __name__ == "__main__" : str = "geeksforgeeks"; prCharWithFreq(str); # This code is contributed by 'Ankur Tripathi'
C#
// C# implementation to // print the characters and // frequencies in order // of its occurrence using System; using System.Collections; using System.Collections.Generic; class GFG { public static void prCharWithFreq(string s) { // Store all characters and // their frequencies in dictionary Dictionary<char,int> d = new Dictionary<char,int>(); foreach(char i in s) { if(d.ContainsKey(i)) { d[i]++; } else { d[i]=1; } } // Print characters and their // frequencies in same order // of their appearance foreach(char i in s) { // Print only if this // character is not printed // before if(d[i] != 0) { Console.Write(i+d[i].ToString() + " "); d[i] = 0; } } } // Driver Code public static void Main(string []args) { string s="geeksforgeeks"; prCharWithFreq(s); } } // This code is contributed by pratham76
Javascript
<script> // Javascript implementation to //print the characters and // frequencies in order // of its occurrence function prCharWithFreq(s) { // Store all characters and // their frequencies in dictionary var d = new Map(); s.split('').forEach(element => { if(d.has(element)) { d.set(element, d.get(element)+1); } else d.set(element, 1); }); // Print characters and their // frequencies in same order // of their appearance s.split('').forEach(element => { // Print only if this // character is not printed // before if(d.has(element) && d.get(element)!=0) { document.write( element + d.get(element) + " "); d.set(element, 0); } }); } // Driver Code var s="geeksforgeeks"; prCharWithFreq(s); </script>
g2 e4 k2 s2 f1 o1 r1
Complejidad de tiempo: O(n), donde n es el número de caracteres de la string.
Espacio Auxiliar: O(n),
Método #3: Usando la programación Orientada a Objetos:
Podemos resolver este problema sin usar un HashMap también. Pero luego tenemos que crear nuestra propia clase cuyos objetos tendrán 2 propiedades: el carácter y su ocurrencia.
- Creamos una clase en este caso llamada CharOccur e inicializamos 2 variables carácter y ocurrencia en su constructor.
- En la parte principal de nuestra clase original, simplemente crearemos una lista que pueda almacenar estos objetos.
lógica –
- Bucle a través de la cuerda.
- Compruebe si el carácter actual de la string ya está presente en algún objeto. Si está presente, incremente su ocurrencia; de lo contrario, establezca su ocurrencia en 1.
Java
/*package whatever //do not write package name here */ import java.io.*; import java.util.ArrayList; class GFG { public static void main(String[] args) { String s1 = "GFG"; System.out.println("For " + s1); frequency(s1); String s2 = "aaabccccffgfghc"; System.out.println("For " + s1); frequency(s2); } private static void frequency(String s) { if (s.length() == 0) { System.out.println("Empty string"); return; } ArrayList<CharOccur> occurrences = new ArrayList<CharOccur>(); // Creating ArrayList of objects of Charoccur class for (int i = 0; i < s.length(); i++) { /* Logic * If a pair of character and its occurrence is * already present as object - increment the * occurrence else create a new object of * character with its occurrence set to 1 */ char c = s.charAt(i); int flag = 0; for (CharOccur o : occurrences) { if (o.character == c) { o.occurrenece += 1; flag = 1; } } if (flag == 0) { CharOccur grp = new CharOccur(c, 1); occurrences.add(grp); } } // Printing the character - occurrences pair for (CharOccur o : occurrences) { System.out.println(o.character + " " + o.occurrenece); } } } // Creating a class CharOccur whose objects have 2 // properties - a character and its occurrence class CharOccur { char character; int occurrenece = 0; CharOccur(char character, int occurrenece) { this.character = character; this.occurrenece = occurrenece; } } // Contributed by Soham Ratnaparkhi
For GFG G 2 F 1 For GFG a 3 b 1 c 5 f 3 g 2 h 1
Análisis de complejidad:
- Complejidad de tiempo: O(n), donde n es el número de caracteres de la string.
- Espacio Auxiliar: O(n)
Método n.º 4: uso de funciones integradas de Python:
Podemos resolver este problema rápidamente usando el método python Counter() . El enfoque es muy simple.
1) Primero cree un diccionario usando el método Counter que tenga strings como claves y sus frecuencias como valores.
2) Recorra en este diccionario las claves de impresión junto con sus valores
Python3
# Python3 implementation to print the characters and # frequencies in order of its occurrence from collections import Counter def prCharWithFreq(string): # Store all characters and their # frequencies using Counter function d = Counter(string) # Print characters and their frequencies in # same order of their appearance for i in d: print(i+str(d[i]), end=" ") string = "geeksforgeeks" prCharWithFreq(string) # This code is contributed by vikkycirus
g2 e4 k2 s2 f1 o1 r1
Este artículo es una contribución de Ayush Jauhari . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA