How to resolve the Max Char Algorithm

#programming #javascript #algorithms #datastructures

Welcome back, algorithm enthusiasts! I hope you've been studying hard.

Last week, we counted the vowels in a string and learned how to identify each character. This time, we're going further by finding the max character in a string. This is another common challenge frequently encountered in technical interviews.

Problem Statement

Given a string, return the character that is most commonly used in the string.

Building on our previous lesson, we'll apply what we learned about looping through strings and character identification. Previously, we counted specific characters from a predefined list. Now, we're advancing to find the most frequent character in a string. While the underlying concept is similar, this challenge is more complex as it requires mapping and tracking each unique character's frequency rather than just counting specific ones.

As usual, the problem statement gives us the input and the desired output: a string, and the character with the highest frequency.

Algorithm to solve it

First of all, we need to declare 3 variables: a Map for store each char and his occurrencies, a string to store the most frequent char and finally, an integer to store the max count of all.

const charMap = new Map<string, number>();
let maxChar = '';
let maxCount = 0;

We could use a simple object to map characters, but Maps offer several advantages over objects. While objects work fine for basic needs, a more complex solution will benefit from using the Map object.

Next, iterate through each character in our string using the good old for...of loop

for (const char of str) {}

Now, for each iteration, we need to update our character count. Create a count const to store each character's occurrence. We'll access the character key in our charMap. If the character exists, we increment its count by one. If not, we start with zero and increment by one. This can be done with a one liner.

const count = (charMap.get(char) ?? 0) + 1;

Then, update the charMap with the character and its count. This will either override the existing value with the new count or create a new entry with the character and initialize its count to one.

charMap.set(char, count);

However, we still have more to do. Because we need to find the maxChar, and we just checked the char occurrence. So, we need to check if the current count, for this char in the iteration is higher than the maxCount

if (count > maxCount)

If it's higher, update the maxCount variable with the current count and the maxChar variable with the current character. This ensures we always track the character with the highest occurrence as we progress through the string. Easy, right?

maxCount = count;
maxChar = char;

If the count is lower than maxCount, the loop continues to the next iteration while our maxCount and maxChar variables remain unchanged. Finally, after we've looped through the entire string, we have our maxChar ready to return.

return maxChar;

Typescript implementation

Here's the complete solution implemented in TypeScript:

export function maxChar(str: string): string {
    const charMap = new Map<string, number>();
    let maxChar = '';
    let maxCount = 0;

    for (const char of str) {
        const count = (charMap.get(char) ?? 0) + 1;
        charMap.set(char, count);
        if (count > maxCount) {
            maxCount = count;
            maxChar = char;
        }
    }

    return maxChar;
}

Conclusion

In this post, we've tackled another fundamental algorithmic challenge: finding the most frequently occurring character in a string. This algorithm builds upon our previous knowledge of string manipulation and introduces the concept of frequency mapping using JavaScript's Map object.

The solution we've implemented is both efficient and straightforward, with a time complexity of O(n) where n is the length of the input string. We only need to traverse the string once, updating our character counts and tracking the maximum as we go.

Beyond technical interviews, this pattern of finding the most frequent element appears in various real-world applications, from text analysis to data compression algorithms. Understanding this concept will serve you well in your programming journey.

Next week, we'll take a break from algorithms to explore the Hash Table data structure, which we've already utilized in this exercise.

And remember, you can check this and another algorithms in my repo: https://github.com/RubenOAlvarado/algorithms

Until then, happy coding!