Description: Write a program to find the maximum occurring character in an input string.

 
If video does not load, Click here
 
Example:

Input String: “ipupilis”

Character ‘i’ is the maximum occurring character.

Algorithm:

1) Create an array ‘count’ and initialize each element to 0. The array ‘count’ stores the number of times each character occurs. So if character ‘k’ occurs 5 times, count[‘k’] is equal to 5.

2)Scan the string from left to right incrementing count corresponding to the character being scanned.

Repeat count[S[i]]=count[S[i]] + 1
              for all values of ‘i’.

3)Initialize ‘max’ as the count of the first element of the string and ‘x’ as the first character.

Scan through the remaining string S using index ‘i’ comparing the value of the corresponding value of ‘count’ with ‘max’ and updating:

 if(count[S[i]] > max)

         max=count[S[i]];

         x=S[i];

4)’x’ stores the maximum occurring character in the string.

Implementation in C:

/*The following function returns the maximum occuring character.*/

char maxoccuring(char String[])

{

int count[256];

int i,j;

 

for (i=0;i<256;i++)

{

  count[i]=0;

}

for (i=0;i<strlen(String);i++)

{

  count[String[i]]=count[String[i]]+1;

}

int max;

char x;

x=String[i];

max=count[String[0]];

for(i=0;i<strlen(String);i++)

{

  if(count[String[i]]>max)

  {

            max=count[String[i]];

            x=String[i];

  }

}

return x;

}

Time Complexity:

O(n)

Go to top