Frequency of each character in a string using map in c++
In some competitive programming problems, it is required to check if a character in a string is repeating or not, number of repeating character or frequency of a particular character or all characters in a string.
So, in this C++ tutorial, we are going to discuss how to find the frequency of each character in a string using map.
Frequency of characters in a string in c++ using map
What is map ?
Map are the containers which stores elements in mapping way. There is a key value and a unique map value for it.
It prints the value in the sorted order of the key value.
Syntax:
map<data_type of key value , data_type of mapping value>alias_name for map;
Ex:
map<char,int>m;
What is iterator?
An iterator is a pointer which points to elements in CPP Standard Template Library (STL). We use iterators in c++ to move through the elements in containers.
Syntax:
container<Data_type 1,Data_type 2>::iterator alias_name
Ex:
map<char,int>::iterator itr;
Iterators reduce the time complexity of a program.
Operations of iterators :-
1. begin() :- begin() is used to return beginning position of container.
2. end() :- end() is used to return after end position of container.
Algorithm to find out the frequency of a character in C++ using map
- Declare a map of char to int where key values are the characters of the string and mapped values are its frequencies.
- Read the characters from first to last in the string and increment the value in the map while reading each characters.
- As map do not contains duplicate keys , so finally, our map stores unique key which is characters in string uniquely and its mapped value which is the frequency of each character.
- To print values in the map we declare an iterator , and print the value of itr->first ( characters in a string) and itr->second (their frequencies) till itr does not reach the end of the map.
Code to count frequency of each character in a string using map in CPP
#include<bits/stdc++.h> using namespace std; int main() { string s; cin>>s; map<char , int >m; map<char , int >::iterator itr; for(long i=0;i<s.length();i++) m[s[i]]++; for(itr=m.begin();itr!=m.end();itr++) cout<<itr->first<<" - "<<itr->second<<endl; }
INPUT
Akarshika
OUTPUT
A - 1 a - 2 h - 1 i - 1 k - 2 r - 1 s - 1
Here, the key values are the characters in the string “Akarshika” and mapping values are its frequencies. Key values are printed in sorted order.
Read also,
m[s[i]]++;
what does this mean?
In “for(long i=0;i -< s.length();i++) { m[s[i]]++; }” we are traversing whole string character by character. In the first iteration, i will be 0 and s[i] will be ‘A’ for the string “Akarshika”. In m[s[i]]++, value of m[s[i]] i.e. m[A] (as s[i]=A for i=0) will increment by 1 (which was initially 0 by default for indices A-Z, a-z ) . So by the end of the first iteration, we will get A-1 pair. similarly all iterations will execute. The reason we will have A-Z, a-z indices because we have used char as the key of our map ‘m’ and we will get the output pairs in alphabetical order. First, we will get pairs of ‘A-Z’ and then we will get pairs of ‘a-z’.
Thanks for this, it was a great help for me
What if I wanted the frequency of one character?
You could repurpose the last for loop in the code above. Instead of using a cout like they did, store the character you’re wanting to find in a char variable and set a counter variable to store the occurrence of the char. After the for loop
cout << char << " : " << counter;
what is the time complexity of this operation?
Also you’d need to compare the iterator value to the character you are looking for while inside the for loop.
char test = ‘t’;
If(*itr == test){
counter++;
}
This is just one way to do it.