Maximum occurring character in a string

Given a string of size n containing lower case letters. We need to find the maximum occurring character in a string. If there is more than one character with a maximum occurrence then print any of them.

Example

Input:

String s=”test”

Output:

Maximum occurring character is ‘t’.

Approach 1: Using Sorting

Main idea

We will first sort the array and then count the frequency of each element and take that character whose count is maximum.

Algorithm for Maximum Occurring Character

1. Declare a variable max_count which will store the maximum count.
2. Initialize a variable count=1 which will store the count the current character.
3. Declare a variable ans which will store our answer.
4. Declare a variable n that stores the length of the input string.
5. Sort the input string.
6. Run a loop for I in range 1 to n
   1. If I is equal to n or s[i] is not equal to s[i-1]
      1. If max_count is strictly less than count, then assign max_count=count and ans=s[i-1].
      2. Assign count=1.
   2. Else increment count by 1.
7. Print ans.

C++ program for Maximum Occurring Character

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin >> s;
    int n = s.length();
    sort(s.begin(), s.end());
    int max_count = 0;
    int count = 1;
    char ans;
    for (int i = 1; i <= n; i++)
    {
        if ((i == n) || (s[i] != s[i - 1]))
        {
            if (max_count < count)
            {
                max_count = count;
                ans = s[i - 1];
            }
            count = 1;
        }
        else
        {
            count++;
        }
    }
    cout <<"Maximum occurring character is "<< ans << endl;
    return 0;
}

tutorialcup

Maximum occurring character is t

JAVA program for Maximum Occurring Character

import java.util.*;
public class Main
{
  public static void main(String[] args) {
      Scanner in = new Scanner(System. in);
      String k = in.nextLine();
      char tempArray[] = k.toCharArray(); 
        Arrays.sort(tempArray); 
        String s = new String(tempArray);
        int n = s.length();
        int max_count = 0;
        int count = 1;
        char ans = '-';
        for (int i = 1; i <= n; i++)
        {
            if ((i == n) || (s.charAt(i) != s.charAt(i - 1)))
            {
                if (max_count < count)
                {
                    max_count = count;
                    ans = s.charAt(i-1);
                }
                count = 1;
            }
            else
            {
                count++;
            }
        }
    System.out.println("Maximum occurring character is "+ans);
  }
}

whattodo

Maximum occurring character is o

Complexity Analysis for Maximum Occurring Character

Time complexity

Sorting the string takes O(N*logN) time and after that, we are traversing the string once. So total time complexity is O(N*logN+N) which is the same as O(N*logN).

Space complexity

We have not used any extra space, so space complexity is O(1).

Approach 2: Using Hashing

Main idea

We will store the frequency of each character in a hash table and after that, we will take the character with the maximum frequency.

Algorithm for Maximum Occurring Character

1. Initialize the hash table of size 256 with zeros.
2. Iterate over the input string and store the frequency of each element in the hash table.
3. Take the character with the maximum frequency as an answer.
4. Print the answer.

Understand with an example

Input string S=”tutorialcup”

After iterating the input string, the hash table will look like this:

Here characters are stored according to their ASCII values.

C++ program

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin >> s;
    vector<int> hash_table(256, 0);
    int n = s.length();
    for (int i = 0; i < n; i++)
    {
        hash_table[s[i]]++;
    }
    int max_count = 0;
    char ans;
    for (int i = 0; i < 256; i++)
    {
        if (hash_table[i] > max_count)
        {
            max_count = hash_table[i];
            ans = i;
        }
    }
    cout <<"Maximum occurring character is "<< ans << endl;
    return 0;
}

programming

Maximum occurring character is g

JAVA program

import java.util.*;
public class Main
{
  public static void main(String[] args) {
      Scanner in = new Scanner(System. in);
      String s = in.nextLine();
        int[] hash_table = new int[256];
        int n = s.length();
        for (int i = 0; i < n; i++)
        {
            hash_table[s.charAt(i)]++;
        }
        int max_count = 0;
        char ans='a';
        for (int i = 0; i < 256; i++)
        {
            if (hash_table[i] > max_count)
            {
                max_count = hash_table[i];
                ans = (char)i;
            }
        }
    System.out.println("Maximum occurring character is "+ans);
  }
}

learning

Maximum occurring character is n

Complexity Analysis for Maximum Occurring Character

Time complexity

As we are iterating over the input string only once, so the time complexity is O(N).

Space complexity

We are using a hash table of size 256 irrespective of the length of the input string. So the space complexity is O(1).

Note: it is not specified in the question, which type of characters the string contains, so we took a hash table of size 256 because there are total 256 ASCII characters.

But for example, if it was given in the question that the input string contains only lowercase alphabets then we could have used a hash table of size 26 only because there are only 26 lowercase alphabets in the dictionary.

References