Maximum occurring character in a string

Maximum occurring character in a string

Problem Statement: Given a string, return the character that occurs the maximum number of times in the string. If the maximum occurrence of two or more characters is the same, return any one of them.

Examples:

Example 1:
Input: str = “takeuforward”
Output: a
Explanation: The character 'a' and 'r’ have the same  maximum occurrence i.e 2. Hence we can print any one of them

Example 2:
Input: str = “apple”
Output: p
Explanation: The character 'p' have the maximum occurrence i.e 2.

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution 1: Using Frequency Array

Approach:
We can store the frequency of characters encountered in the string in the form of their ASCII values. The range of ASCII values can lie from 0 to 256, so we can use an array of size 256 and initialize all the indexes with 0.

For example, a string “apple” will generate a frequency array like below:-

Code:

C++ Code

#include <iostream>
using namespace std;
char maxOccurringChar(string str) {
   char ans;
   int maxfreq = 0, n = str.length();
   int count[256] = {0};
   for (int i = 0; i < n; i++) {
      count[str[i]]++;
      if (count[str[i]] > maxfreq) {
         maxfreq = count[str[i]];
         ans = str[i];
      }
   }
   return ans;
}
int main() {
   string str = "takeuforward";
   cout << "Maximum occurring character is " << maxOccurringChar(str) << endl;
}

Output: Maximum occurring character is a

Time Complexity: O(N) to iterate through an array of size N.

Space Complexity: O(1) because for any input string only a fixed-size array is being allocated.

Java Code

public class Main {
   static char maxOccurringChar(String str) {
      char ans = 'a';
      int maxfreq = 0, n = str.length();
      int count[] = new int[256];
      for (int i = 0; i < n; i++) {
         count[str.charAt(i)]++;
         if (count[str.charAt(i)] > maxfreq) {
            maxfreq = count[str.charAt(i)];
            ans = str.charAt(i);
         }
      }
      return ans;
   }
   public static void main(String[] args) {
      String str = "takeuforward";
      System.out.println("Maximum occurring character is " + maxOccurringChar(str));
   }
}

Output: Maximum occurring character is a

Time Complexity: O(N) to iterate through an array of size N.

Space Complexity: O(1) because for any input string only a fixed-size array is being allocated.

Solution 2: Sorting

Approach: Sort the array so that more than one copy of a character will occupy contiguous positions. We maintain two variables:-

curr_freq to count streak of characters currently being iterated
max_freq to store count of maximum occurring character.

Iterate through the array. At every index there are two situations:-

If the current character is same as previous character : Increment the streak/curr_freq.
If the current character is different from its previous character : Check whether the last streak/curr_freq exceeds max_freq ,if yes update .

Return the character whose frequency was recorded highest.

Dry Run:

Note for beginners: We have used the inbuilt sort function of C++ and Java to perform sorting

Sort function from C++ STL has the following syntax:-

sort(start,end) ,the function performs sorting from start to end -1 index.

Strings in java are immutable. Hence input has to be converted to a character array and sorting is performed on it.

Syntax of sort in java :

Arrays.sort(array_name)

Code:

C++ Code

#include <iostream>
#include <algorithm>
using namespace std;
//Function to find Maximum Occurring Character
char maxOccurringChar(string str) {
   char ans = str[0];
   int i, curr_freq = 0, max_freq = 0, n = str.length();
   for (i = 0; i < n; i++) {
      if (str[i] == str[i - 1]) {
         curr_freq++;
      } 
      else {
         if (max_freq < curr_freq) {
            max_freq = curr_freq;
            ans = str[i - 1];
         }
         curr_freq = 0;
      }
   }
   if (max_freq < curr_freq) {
      max_freq = curr_freq;
      ans = str[i - 1];
   }
   return ans;
}
int main() {
   string str = "takeuforward";
   //sort the string
   sort(str.begin(), str.end());
   cout <<  "Maximum Occurring Character is " << maxOccurringChar(str);
}

Output: Maximum Occurring Character is a

Time Complexity : O(n log n) for sorting and O(n) for one pass.

Space Complexity : O(1)

Java Code

import java.util.Arrays;
public class Main {
   //Function to find Maximum Occurring Character
   static char maxOccurringChar(String str) {
      char ans = str.charAt(0);
      int i, curr_freq = 0, max_freq = 0, n = str.length();
      for (i = 1; i < n; i++) {
         if (str.charAt(i) == str.charAt(i - 1)) {
            curr_freq++;
         } 
         else {
            if (max_freq < curr_freq) {
               max_freq = curr_freq;
               ans = str.charAt(i - 1);
            }
            curr_freq = 0;
         }
      }
      if (max_freq < curr_freq) {
         max_freq = curr_freq;
         ans = str.charAt(i - 1);
      }
      return ans;
   }

   public static void main(String[] args) {
      String str = "takeuforward";
      //convert to character array
      char charArr[] = str.toCharArray();
      //sort the character array
      Arrays.sort(charArr);
      //sorted character array converted back to string
      str = new String(charArr);
      System.out.println("Maximum Occurring Character is " + maxOccurringChar(str));
   }
}

Output: Maximum Occurring Character is a

Time Complexity : O(n log n) for sorting and O(n) for one pass.

Space Complexity : O(1)

Special thanks to Somparna Chakrabarti for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article