Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
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 5th 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.
