Algorithm Action: Frequency Counters

Photo by Olav Ahrens Røtne on Unsplash

Of the many problem-solving approaches there are with algorithms, the one I went over yesterday involved using frequency counters. With them, we can keep track of the number of times a certain alphanumeric character, for example, occurs. Afterward, we can use those frequencies to determine solve the problem.

Let’s check out an example!

Anagrams

A somewhat common, easier question, anagram problems usually task us with comparing two strings to check if they’re anagrams of one another.

Given two strings, write a function to determine if the second string is an anagram of the first. An anagram is a word, phrase, or name formed by rearranging the letters of another, such as cinema, formed from iceman.

The principal characteristic of the frequency counter approach involves initializing an object that keeps track of number of times a letter appears in a string.

function validAnagram(firstString, secondString) { 
      const lookup = {}; 
}

Then, instead of using slower, nested loops, we’re going to create two separate loops, a faster solution. The first loop will loop over the first string, and the second loop will loop over the second string. Each loop, however, will have a different purpose. See below:

//loop over first string to populate lookup variable with data 
    for (let i = 0; i < first.length; i++) { 
        let letter = first[i]; 
        //if letter is found, add 1 to value. 
        //otherwise initialize it with value of 1
        lookup[letter] ? lookup[letter] += 1 : lookup[letter] = 1; 
    }
//loop over second string to compare with lookup object 
    for (let i = 0; i < second.length; i++) { 
        let letter = second[i]; 
        //if unable to find letter OR letter is 0, 
        //both inputs aren't anagrams
        if (!lookup[letter]) { 
            //!lookup[letter] with a value of 0 is falsey,
            //so no need to explicitly check for 0
            return false
        } else { 
            lookup[letter] -= 1; 
        }
    }

The purpose of the first loop is to create the object that the second loop will use. For instance, if our string is “heavy”, the the lookup object becomes

const lookup = {"h": 1, "e": 1, "a": 1, "v":1, "y": 1}

The second loop compares the second string to this object. If there is a matching character in the lookup object, we reduce its key by 1. If the letter is not in the object at all or if it is but at zero, we’re done and it is not an anagram. All together, the function ends up looking like this:

function validAnagram(first, second){ 
    //check to see if length is different
    if (first.length !== second.length) { 
        return false;
    }
    //object initialized to track frequency
    const lookup = {};
    //loop over first string to populate lookup variable with data 
    for (let i = 0; i < first.length; i++) { 
        let letter = first[i]; 
        //if letter is found, add 1 to value. 
        //otherwise initalize it with value of 1
        lookup[letter] ? lookup[letter] += 1 : lookup[letter] = 1; 
    }
    //loop over second string to compare with lopokup object 
    for (let i = 0; i < second.length; i++) { 
        let letter = second[i]; 
        //if unable to find letter OR letter is 0, 
        //both inputs aren't anagrams
        if (!lookup[letter]) { 
            //!lookup[letter] with a value of 0 is falsey,
            //so no need to explicitly check for 0
            return false
        } else { 
            lookup[letter] -= 1; 
        }
    }
    return true; 
}

What do you think? If you liked what you read, consider connecting or dropping me a line at nick.echev@gmail.com!