Wednesday, 5 April 2017

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:



EmoticonEmoticon