# C Program to find which character occurs the maximum number of times in a string in O(n) time

In this program a string is given to us which comprises of lower case alphabets (a-z), upper case alphabets (A-Z) and special characters like !,<,...,#.

Our approach is simple we will use concept of hashing. In this program we used STL unordered_map <char,int>, where character of the string is working as a key to the number of its occurrences. C++ Program to find which character occurs the maximum number of times is given below. This program is successfully executed and tested on online compiler.

Algorithm:

step 1:  We will traverse the sring and increment the count of the character at current index
step 2:  Traverse the string again and keep track of the key where count is maximum.
/* If count of two character (keys in map) is same then compare their ASCII value and choose the character with lower ASCII value.

For example:-

Let the string is:   aabccda
Then the unordered_map for above string is:

length of the string is 'l'= 7

Traversing the string:

For i=0 to len(string)

Pass 1, i=0:    string[i]=string[0]=a,  Therfore map m will be incremented at
key string[0]  m[string[0]]++ =  map(a,1);

Pass 1, i=1:    string[i]=string[1]=a,  Therfore map m will be incremented at
key string[1]  m[string[1]]++ =  map(a,2);

Pass 1, i=2:    string[i]=string[2]=b,  Therfore map m will be incremented at
key string[2]  m[string[2]]++ =  map(b,1);

Pass 1, i=3:    string[i]=string[3]=c,  Therfore map m will be incremented at
key string[3]  m[string[3]]++ =  map(c,1);

Pass 1, i=4:    string[i]=string[4]=c,  Therfore map m will be incremented at
key string[1]  m[string[4]]++ =  map(c,2);

Pass 1, i=5:    string[i]=string[5]=d,  Therfore map m will be incremented at
key string[5]  m[string[5]]++ =  map(d,1);

Pass 1, i=6:    string[i]=string[6]=a,  Therfore map m will be incremented at
key string[6]  m[string[6]]++ =  map(a,3);

PROGRAM:

```#include <iostream>
#include <unordered_map>
#include <stdio.h>
#include <string.h>
using namespace std;

int main()
{
std::string s;
getline(cin,s);  /*taking input */
std::unordered_map <char,int> m;
for(int i=0;i<s.length();i++)
{
m[s[i]]++;
}
int max;
char c;
max=m[s[0]];
c=s[0];
for(int i=1;i<s.length();i++)
{
if(m[s[i]]>=max)
{
if(m[s[i]]==max)
{
if(s[i]<c)
{
c=s[i];
}
}
else
{
max=m[s[i]];
c=s[i];
}
}
}
printf("%c %d",c,max);
return 0;
}
```

OUTPUT: