LeetCode: Valid Anagram

This week’s coding challenge comes from Leetcode, the Valid Anagram challenge. The function you’re required to create in this challenge will take in two different strings and return true if they’re anagrams of each other. In this blog post I’ll break down two different ways to solve this problem. One single line function completed through chaining JavaScript methods, and another through creating an object.

The simplest answer, to me, would be to chain methods onto the passed-in strings to check if they’re equal. An anagram is a word that is created by rearranging the letters of another word, so if the two strings are equal to each other when they’re sorted alphabetically. Since the JavaScript sort() method can only be used on an array, I’ll need to split the string into an array, sort that array, then rejoin the array into a string.

This solution is pretty simple and compact. It’s a solid answer, but not the most creative one. I knew I could come to a solution using an object, creating an object with keys of the characters in one string, and values of the number of times that character occurs in the string. First I’d create an empty object, the loop I’d use to populate this object is a pretty standard format.

Before going further, I want to account for a fringe case that will result in a false return. If the strings are different lengths, it’s impossible for the two to be anagrams of each other. I want to check this before looping and populating the object, so I’ll do that at the top of the function.

After the object is created I’m going to loop through the next string to check each key in the object. To start, if the current character in the string doesn’t exist as a key, then the function will end and return false. When the character does exist as a key, I want to reduce that value by 1. If the value is reduced and the key’s current value is 0, then I’ll delete that key from the object. If an object is an anagram, then at the end of the loop the object will be empty again.

Finally, at the end, I want the function to return true if the object ends up being empty. Since the function uses two loops next to each other, instead of two nested loops, the function’s Big O Time Complexity ends up being O(2n), or simplified to O(n) since both have the same growth rate.