The Ultimate Guide to JavaScript Algorithms: Finding the Most Recurring Character

Publikováno: 23.1.2019

In this challenge, we will be dealing with strings, arrays and objects. We will learn to manipulate these data types using various methods that'd bring us to a working solution in the end.

E...

Celý článek

In this challenge, we will be dealing with strings, arrays and objects. We will learn to manipulate these data types using various methods that'd bring us to a working solution in the end.

Enough talk, Let's dive right in!

You should already have your development environment setup for this course. Update your cloned repository by running the command git pull. Inside the Beginner folder, navigate to the maxRecurringChar folder. Our work for this challenge will be done in here. Make sure to follow along in the index-START.js file.
The Challenge
Given a string of text, find and return the most recurring character. e.g

maxRecurringChar('aabacada') // will return 'a'

Pretty simple, yeah?

Algorithmic Thinking

From the challenge statement, we can infer that our function has only one parameter; the string of text.

We need to somehow keep track of every character in the string as well as the number of times it exists. This we would describe as character mapping. Once we successfully create such a map, we can easily determine which character has the highest occurence.

Code Implementation

From our thought process, you would notice that there is one thing that is very important if we are to come up with a fitting solution to this problem.

We need to keep track of every character in the string as well as the number of times it exists.

How do we do this?

Character Mapping

Imagine you were given a bag of balls of the following colors; green, red, blue and yellow. Your task is to sort them. Intuitively, you would have to bring the balls out of the bag and group them in isolation according to color. In the end, it is counting these groups of like-colored balls that'd help you ascertain what number of each color exists and by extension the most recurring color.

Congratulations! You mapped the balls successfully. Now let's perform same magic with characters.

Our intention is to map characters to the number of times they exist as shown below. If we had a string of text ‘aaabbbcdcb’, we would have:

a= 3
b=4
c=2
d=1

To implement this, an object comes in very handy. We loop through the text received and add each character to a character map object as a key and the number of times it exists as a value. The object would look like this:

let charMap = {
    a:3,
    b:4,
    c:2,
    d:1
}

Here's how we create such an object from a string of**text**:

let charMap = {};

for (let char of text) {
    if (charMap.hasOwnProperty(char)) {
        charMap[char]++
    } else {
        charMap[char] = 1;
    }
}

Having initialized charMap to an empty object, we use a for…of loop to iterate through the string of text. For every character, we check if it has been mapped already(is a property of the charMap object) by calling the .hasOwnProperty() method on the object. If it is, we increment its value, otherwise it is added as a property and its value is set to 1.

Having created our character map, we can now focus on actually solving the problem. We need to return the character that is most recurring. Let us now consider two ways to do this.

For…in Iteration

JavaScript offers various ways to loop through iterable objects.

An iterable object is basically a collection of consistently formatted data. Examples include strings, arrays, array-like objects etc.The for…in statement iterates over all non-Symbol,enumerable propertiesof an object.

See how we use it below:

function maxRecurringChar(text) {
    let charMap = {}
    let maxCharValue = 0
    let maxChar = ''

    for (let char of text) {
        if (charMap.hasOwnProperty(char)) {
            charMap[char]++
        } else {
            charMap[char] = 1
        }
    }

    for (let char in charMap) {
        if (charMap[char] > maxCharValue) {
            maxCharValue = charMap[char]
            maxChar = char
        }
    }

    return maxChar
}

You'd notice that within the maxRecurringChar function above, we use the snippet earlier considered to generate a character map of the received string of text.

For looping through the charMap object, we initialize two variables at the beginning.

maxCharValue is used to store the maximum value yet encountered at the point of every iteration with the for…in loop.
maxChar is used to store the character with the highest value on every iteration.

As we run through with the for…in loop, we check if the character being evaluated has a greater value than our maxCharValue which is initially zero. If it is, it becomes the new maxCharValue and the character is stored in maxChar. If it is not, we move on to the next character.

At the end, we return maxChar which now holds the character with the highest value, thus the most recurring.

Capische? Let’s now try some other way.

Forming Arrays from the Character Map

In ES6, we are able to perform various computations on objects by converting them to arrays first.

ES6 is basically EcmaScript 6 / EcmaScript 2015. EcmaScript is simply a standard that JavaScript is based upon. So, ES6 is a new version or new standard of JavaScript. ES6 brings many new feature like concept of classes, template tags, arrow functions etc.

Let's see how this works:

function maxRecurringChar(text) {
    let charMap = {}
    let charArray =[]
    let vaulesArray = []
    let maxCharValue = 0

    for (let char of text) {
        if (charMap.hasOwnProperty(char)) {
            charMap[char]++
        } else {
            charMap[char] = 1
        }
    }

    charArray = Object.keys(charMap)
    vaulesArray = Object.values(charMap)
    maxCharValue = Math.max(...vaulesArray)

    return charArray[vaulesArray.indexOf(maxCharValue)]
}

In the code snippet above, again we create a character map with the snippet of code initially considered. Next, we use ES6 syntax to form arrays from the character map. First an array of the keys of the charMap(all characters in the text) known as charArray and then an array of the values(number of occurences) known as valuesArray arranged in corresponding order.

For the character map we visualized earlier(i.e ‘aaabbbcdcb’), we'd have something like this:

charArray = ['a', 'b', 'c','d']
valuesArray = [4,3,2,1]

Next we use the built in Math.max() function to find the maximum value in the array of values and we store this value in a variable maxCharValue.

Finally we use the .indexOf() method to search the valuesArray for the position of the maxCharValue. This is necessary as the position of the maxCharValue in valuesArray corresponds to the position of the character in the charArray with that number of occurrences.

Thus, on getting the index(position), we return the character holding the same position in the charArray. This is the highest recurring character.

We finally made it! Now let's test our solutions.

Testing

Testing Correctness with Jest For each solution above, run the command below to start the tests:

npm run test maxRecurringChar

Here are the results:

For…in Iteration
Forming Arrays from the Character Map

We should celebrate, both solutions passed in all cases.

Testing Performance with JSPerfHere on JSPerf, we compare both solutions to see which performs better. See the results below:

Always try out tests on your own to ensure you have similar results. The result as shown above leads us to the conclusion that:

The For…In iteration is the fastest. With the Arrays method trailing behind by approximately 30%.

Practical Application

You will find the techniques considered in this challenge handy for JavaScript Interviews and code challenges. Furthermore, they can be used at a more advanced level in Search Engine Optimization(SEO) for determining the keyword density in a piece of content.

Conclusion

From this challenge, we have learnt to manipulate objects intelligently using various JavaScript techniques. We considered two ways to solve the challenge and determined that the For…in loop is better optimized.

Still, both solutions considered work perfectly and may be used in an interview situation.