Algorithm Time: Anagrams

Daniela Sandoval
Nov 4 · 6 min read

An algorithm that will take you back to your bananagram days.

If you missed it, ‘nag a ram’ is an anagram for anagram!

As mentioned in my previous post, I will be diving into the world of algorithms and invite you all to tag along. There’s strength in numbers, especially for my bootcamp grads out there. This week I got a nasty cold so I didn’t get too far into Colt Steele’s algorithm course , but I encountered my first solo algo problem. It wasn’t one of the crazier ones, so I gladly accepted the challenge. In today’s blog post, I will be creating an algorithm that validates given inputs as anagrams. If you’re not familiar with anagrams, they are rearranged words/phrases that are made of another word/phrase’s letters. For example: cat and act , maple and ample . In order for us to test whether or not something is an anagram, we need some sort of comparison device for our two inputs or better yet, we could write an algorithm!

The Problem 🤷🏻‍♀️

So what does our initial prompt look like?

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 and iceman.

Let’s restate this prompt. We are writing a function that checks if two strings are anagrams. Boom. Easier said than done right? Our prompt gives us a couple of directions despite being two sentences. The first being that our end result will more than likely be a “yes/no” response or in our case, a boolean of true or false . The second is that the focus of our solution will revolve around alphabetical characters. Third, the logic behind our algo will involve comparing the contents of one input with another so we’ll definitely be using loops. The last point to notice is about anagrams themselves. One of the rules for anagrams is that ALL letters have to be used, including the repeated letters.

As for inputs and outputs, what we want to happen is that inputs like cat and tac will output true , but cat and dog will output false . Another case to account for are phrases. Inputs like school master and the classroom should also output true . We’ll forego edge cases in which one of the inputs might be an empty string or numerical values and assume that all is well and that our inputs will definitely be string data types (definitely important to ask your interviewer if you’re doing a real interview!).

Breaking It Down 🕺🏻

Diving straight into coding after reading a prompt always results in me going back to re-read the problem, deleting blocks of code because it’s not what the prompt was asking for, or getting confused as to what I should do next. Breaking things down into smaller tasks helps not only to give yourself direction, but also helps interviewers see your thought process. For our anagram problem I broke it up into 5 steps. This is also starting from: 1. logic stuff, 2. return an answer of true or false. Your approach might look different than mine, but this is the process I came up with for my solution. As I came up with steps, I also began thinking about smaller details to look into later. The point is to create a road map of how your solution will work.

function anagrams(input A, input B) {
1. Establish counters (object).
2. Loop through first array to make the first counter.
a. Use conditional block to determine if the letter is in our counter object (use shorthand/ternary???).
b. Consider where you want to convert to lowercase and test for ALPHABETICAL values.

3. Repeat the same step for the second array and second counter.
4. Create final loop that will check to see if letters from the FIRST input are in the SECOND input based on 2 conditions.
a. Whether or not the key/letter exists in the second string.
b. Making sure the frequency of that letter (once it does exist) is the same in both strings.

5. If the all letters pass the test, return true that it is a valid anagram.
}

Let’s Code! ⌨️

Now that we have a clearer idea of what we’re doing, it’s time to turn our text into code.

Our first step: establish counters is needed because we want to create a way for us to see what letters are used and how many times they appear in our input. We want to create something that we can use as a reference point of what our inputs look like that’ll resemble {a: 1, c:1, t: 1} .

1. Establish counters (object).  
let frequencyCounter1 = {}
let frequencyCounter2 = {}

Second step and third step: looping through our first array to create a counter object . We are going to create an object that is made by looping through our first array and checking to see if our current letter is a key in our counter object. If it is a key, we will add increase our counter by 1, if it isn’t, we will create a new key with an initial count of 1. You can start out with a classic for loop, but I used a for...of statement after my first refactoring. Since anagrams can also include phrases, this means that our lovely string might not be one word so we only want to care about letters and not spaces. For the sake of time, I used a regular expression to only test for letters. If it passed the test, then I either add on to the current letter count OR I created a new key with that letter. The third step is the part that could be DRY-er about my code, but it’s okay for now since we are creating this algo because it asks for only two inputs.

2/3. Loop through first array to make the first counter.  
for(let letter of stringA) {
a. Lowercased here for uniformity and dryness
let char = letter.toLowerCase()
if(/[a-z]/.test(char)) {
a. Conditional block that determines if the letter is in our counter object. If it is, add one to it, if not set it at zero so we can start at 1.
frequencyCounter1[char] = (frequencyCounter1[char] || 0) + 1
}
}

Fourth step: create a final loop that will compare both counter objects to see if they match . An important thing to note is that our counters are objects rather than arrays. The difference is that we can iterate smoothly through arrays with our for loop, but we run into trouble if we try it with a object. In order to get an array out of our counter object, I satisfied the first of our conditions by checking if our keys (letters) are all in both counter objects by collecting them using Object.keys() . If we don’t get the same letters in both objects, it’s not an anagram and it returns false . If all letters are the same, then we have to test for the frequency or the amount of times they appeared by comparing each of the values of the same key. If they we don’t get the same number, low and behold, it’s not an anagram.

4. Create final loop that will check to see if letters are in both counter objects.
for(let key of Object.keys(frequencyCounter1)) {
a. Whether or not the key/letter exists in the second string.
if(!frequencyCounter2[key]) {
return false
}
b. Making sure the frequency of that letter (once it does exist) is the same in both strings.
if (frequencyCounter1[key] !== frequencyCounter2[key]) {
return false
}
}

Fifth step: return true if it really is an anagram is what we’ve been waiting for this entire time. If our counter objects match in both letter and frequency, then we can finally output true .

5. Return true if it really is an anagram 🎉  
return true

Our Anagram Solution 💡

Final Thoughts ☕️

At the end of it all, I refactored my code about three times. Some of it was for stylistic purposes, while others were for functionality as I kept thinking of smaller conditions along the way. In the future, I’d like to make my solution a bit more DRYer when creating my second counter. Going back to our friend Big O Notation, my algo would have a time complexity of O(N) because I have three separate loops as opposed to nested ones. Space wise, they’ll definitely take up more space since both my objects will increase especially in regards to letter frequency (thank goodness for a 25 letter alphabet). Although I did take up a bit more time than I anticipated, algorithms definitely end up teaching you more than 1 new skill. Hopefully after this anagram algorithm you can go from sobs to boss !

Daniela Sandoval

Written by

Software Developer | Flatiron Alumni | Proud cat mom! 🐈 💻 ✨

JavaScript in Plain English

Learn the web's most important programming language.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade