Given a string str, the task is to print the frequency of each of the characters of str in alphabetical order.
Example:
Input: str = “aabccccddd”
Output: a2b1c4d3
Since it is already in alphabetical order, the frequency
of the characters is returned for each character.
Input: str = “geeksforgeeks”
Output: e4f1g2k2o1r1s2
Approach:
- Create a Map to store the frequency of each of the characters of the given string.
- Iterate through the string and check if the character is present in the map.
- If the character is not present, insert it in the map with 1 as the initial value else increment its frequency by 1.
- Finally, print the frequency of each of the character in alphabetical order.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
const int MAX = 26;
void compressString(string s, int n)
{
int freq[MAX] = { 0 };
for ( int i = 0; i < n; i++) {
freq[s[i] - 'a' ]++;
}
for ( int i = 0; i < MAX; i++) {
if (freq[i] == 0)
continue ;
cout << ( char )(i + 'a' ) << freq[i];
}
}
int main()
{
string s = "geeksforgeeks" ;
int n = s.length();
compressString(s, n);
return 0;
}
|
Java
class GFG
{
static int MAX = 26 ;
static void compressString(String s, int n)
{
int freq[] = new int [MAX] ;
for ( int i = 0 ; i < n; i++)
{
freq[s.charAt(i) - 'a' ]++;
}
for ( int i = 0 ; i < MAX; i++)
{
if (freq[i] == 0 )
continue ;
System.out.print(( char )(i + 'a' ) + "" + freq[i]);
}
}
public static void main (String[] args)
{
String s = "geeksforgeeks" ;
int n = s.length();
compressString(s, n);
}
}
|
Python3
MAX = 26 ;
def compressString(s, n) :
freq = [ 0 ] * MAX ;
for i in range (n) :
freq[ ord (s[i]) - ord ( 'a' )] + = 1 ;
for i in range ( MAX ) :
if (freq[i] = = 0 ) :
continue ;
print (( chr )(i + ord ( 'a' )),freq[i],end = " " );
if __name__ = = "__main__" :
s = "geeksforgeeks" ;
n = len (s);
compressString(s, n);
|
C#
using System;
class GFG
{
static int MAX = 26;
static void compressString( string s, int n)
{
int []freq = new int [MAX] ;
for ( int i = 0; i < n; i++)
{
freq[s[i] - 'a' ]++;
}
for ( int i = 0; i < MAX; i++)
{
if (freq[i] == 0)
continue ;
Console.Write(( char )(i + 'a' ) + "" + freq[i]);
}
}
public static void Main()
{
string s = "geeksforgeeks" ;
int n = s.Length;
compressString(s, n);
}
}
|
Javascript
<script>
let MAX = 26;
function compressString(s, n)
{
let freq = new Array(MAX);
freq.fill(0);
for (let i = 0; i < n; i++)
{
freq[s[i].charCodeAt() - 'a' .charCodeAt()]++;
}
for (let i = 0; i < MAX; i++)
{
if (freq[i] == 0)
continue ;
document.write(String.fromCharCode(i +
'a'.charCodeAt()) + "" + freq[i]);
}
}
let s = "geeksforgeeks" ;
let n = s.length;
compressString(s, n);
</script>
|
Time Complexity: O(n)
Auxiliary Space: O(1)
Using Map(stl):-
The Approach:
The approach is very simple we are go on traversing and print the all the char with there frequency.
C++
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int main() {
string s = "geeksforgeeks" ;
map< char , int >mp;
for ( auto it:s)mp[it]++;
cout<< "All character in string with there frequency :" <<endl;
for ( auto it:mp)cout<<it.first<<it.second;
return 0;
}
|
Python3
s = "geeksforgeeks"
mp = {}
for i in range ( len (s)):
if (mp.get(s[i]) ! = None ):
mp[s[i]] = mp.get(s[i]) + 1
else :
mp[s[i]] = 1
myKeys = list (mp.keys())
myKeys.sort()
mp = {i : mp[i] for i in myKeys}
for i in mp:
print (i, end = "")
print (mp[i], end = "")
|
C#
using System;
using System.Collections.Generic;
class GFG {
static void Main( string [] args) {
string s = "geeksforgeeks" ;
Dictionary< char , int > mp = new Dictionary< char , int >();
foreach ( char c in s) {
if (mp.ContainsKey(c)) {
mp++;
} else {
mp = 1;
}
}
Console.WriteLine( "All character in string with their frequency:" );
foreach (KeyValuePair< char , int > pair in mp) {
Console.Write(pair.Key + "" + pair.Value);
}
}
}
|
Javascript
let s = "geeksforgeeks" ;
let mp = new Map();
for (let i = 0; i<s.length; i++){
if (mp.has(s[i])){
mp.set(s[i], mp.get(s[i])+1);
} else {
mp.set(s[i], 1);
}
}
console.log( "All characters in string with there frequency : " );
var unsortedArray = [ ...mp];
var sortedArray = unsortedArray.sort(([key1, value1], [key2, value2]) => key1.localeCompare(key2))
mp = new Map(sortedArray)
mp.forEach( function (value, key){
console.log(key+value);
})
|
Java
import java.util.*;
public class Main {
public static void main(String[] args) {
String s = "geeksforgeeks" ;
Map<Character, Integer> mp = new TreeMap<Character, Integer>();
for ( char c : s.toCharArray()) {
if (mp.containsKey(c)) {
mp.put(c, mp.get(c) + 1 );
} else {
mp.put(c, 1 );
}
}
System.out.println( "All character in string with their frequency :" );
for (Map.Entry<Character, Integer> entry : mp.entrySet()) {
System.out.print(entry.getKey() + "" + entry.getValue());
}
}
}
|
Output
All character in string with there frequency :
e4f1g2k2o1r1s2
Complexity Analysis:
Time Complexity: O(n),for tarversing string.
Auxiliary Space: O(n),for map.
Approach 3: Recursive approach
Algorithm:
- Take the string “s” as input and calculate size in n.
- Run a loop from ‘a’ to ‘z’ and call the “compressString” function for each time with count = 0 to store the frequency of the letter.
- The “compressString” function check if counter i>size of the string then return the function else increment the count if character equal to s[i] and call the “compressString” again with i+1;
- Now check if count is not equal to 0 then print the letter with count.
C++
#include <bits/stdc++.h>
using namespace std;
void compressString(string s, int n, int i, char letter, int &count)
{
if (i>n-1)
return ;
if (s[i]==letter)
count++;
compressString(s,n,i+1,letter,count);
}
int main()
{
string s = "geeksforgeeks" ;
int n = s.length();
for ( char letter = 'a' ; letter<= 'z' ; letter++)
{
int count = 0;
compressString(s,n,0,letter,count);
if (count==0)
continue ;
cout<<letter<<count;
}
return 0;
}
|
Java
import java.util.*;
class Main {
static void compressString(String s, int n, int i, char letter, int [] count) {
if (i > n - 1 ) {
return ;
}
if (s.charAt(i) == letter) {
count[ 0 ]++;
}
compressString(s, n, i+ 1 , letter, count);
}
public static void main(String[] args) {
String s = "geeksforgeeks" ;
int n = s.length();
for ( char letter = 'a' ; letter <= 'z' ; letter++) {
int [] count = { 0 };
compressString(s, n, 0 , letter, count);
if (count[ 0 ] == 0 ) {
continue ;
}
System.out.print(letter + "" + count[ 0 ]);
}
}
}
|
C#
using System;
class GFG {
static void compressString( string s, int n, int i,
char letter, ref int count)
{
if (i > n - 1)
return ;
if (s[i] == letter)
count++;
compressString(s, n, i + 1, letter, ref count);
}
static void Main()
{
string s = "geeksforgeeks" ;
int n = s.Length;
for ( char letter = 'a' ; letter <= 'z' ; letter++) {
int count = 0;
compressString(s, n, 0, letter, ref count);
if (count == 0)
continue ;
Console.Write(letter);
Console.Write(count);
}
}
}
|
Python3
def compressString(s, n, i, letter, count):
if i > n - 1 :
return
if s[i] = = letter:
count + = 1
compressString(s, n, i + 1 , letter, count)
return count
if __name__ = = '__main__' :
s = "geeksforgeeks"
n = len (s)
for letter in range ( ord ( 'a' ), ord ( 'z' ) + 1 ):
letter = chr (letter)
count = compressString(s, n, 0 , letter, 0 )
if count = = 0 :
continue
print (letter, count, end = '')
|
Javascript
function compressString(s, n, i, letter, count) {
if (i > n - 1) {
return ;
}
if (s.charAt(i) === letter) {
count[0]++;
}
compressString(s, n, i + 1, letter, count);
}
const s = "geeksforgeeks" ;
const n = s.length;
ans = "" ;
for (let letter = "a" ; letter <= "z" ; letter = String.fromCharCode(letter.charCodeAt(0) + 1)) {
const count = [0];
compressString(s, n, 0, letter, count);
if (count[0] === 0) {
continue ;
}
ans = ans +letter + "" + count[0];
} console.log(ans);
|
Time Complexity: O(n)
Auxiliary Space: O(1)
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 geeks!