Algorithm to find the maximum occurring character in a string

Do not miss this exclusive book on Binary Tree Problems. Get it now for free.

Algorithm

Pseudocode

Complexity

Implementation

Applications

Reading time: 15 minutes | Coding time: 5 minutes

One approach to solve this problem would be to sort the input string and then traverse through the sorted string to find the character which is occurring maximum number of times.

We can try a different approach. We can use Hashing to improve the solution. We can keep count of the characters appearing in the string and pick the character with maximum count. We will use an array of length 26 to keep count of the characters. Currently we will only consider the alphabets, we can use this approach for ASCII values also then we would have to use array of size 256.

The hash array for count will be indexed using the character's relative position for letter a. So the count for letter e will be stored in count[5] since e is at 5^th relative from character a

This specific implementation prints multiple characters if there are multiple characters in string with maximum count.

Pseudocode

Input String: 'helloworld'
1. Iterate through string and increment the respective count for each character encountered
    - while iterating, also keep track of the maximum count encountered till now.
    - after this step the count array will be
        - count[3] = 1
        - count[5] = 1
        - count[7] = 1
        - count[11] = 3
        - count[14] = 2
        - count[17] = 1
        - count[22] = 1
2. print all the characters which have count equal to max count

Complexity

Time complexity (in any case): Θ(n)
Space complexity: Θ(1)

Implementation

JavaScript

JavaScript


   const str = 'helloworld';  // input string
    let max = 0; // variable to store the number of appearances of the max char so far
    let maxChars = [];  //array to store to the max char(s) in case of multiple characters
    const charCount = new Array(26).fill(0); // initialize a fixed sized array and fill it with zeros
    // iterate over all the characters and add the count to charCount - just like a hash map
    for(let i = 0;i<str.length;i++){
      const ch = str.charCodeAt(i)-97; //97 is ASCII value of 'a'
      charCount[ch]++;
      if(charCount[ch]>max){
        maxChars = [str.charAt(i)];
        max = charCount[ch];
      }else if(charCount[ch]===max) maxChars.push(str.charAt(i));
    }
    console.log(maxChars.toString()); // print the final answer

Applications

Extended version of this algorithm could be used in frequency analysis of a paragraph in cryptography in which we print all the occurrences of the characters in the string.