Algorithms and Anagrams

Data Structures and algorithms. Everyone in the industry talks about them and they can be very intimidating, especially when put on the spot during a job interview. So I purchased a Udemy course recommended by a friend (https://www.udemy.com/course/js-algorithms-and-data-structures-masterclass/) and started diving in deeper to help me feel more at ease with these types of problems.

Today I want to focus on one particular strategy I learned for figuring out if two strings were anagrams, but one that can also be helpful in any situation where you need to count the number of occurrences. An anagram is a word or phrase that can be formed by rearranging the letters in another word. For example “cinema” can be formed from “iceman” so the two are anagrams.

The problem I was given was to determine the minimum number of deletions needed to make two strings anagrams of each other. The strategy that I learned was to create an object of one of the strings with a count of how many times each letter was used and then see if the same count existed in the other string. Then count the leftover letters for the deletions that need to happen. Let’s dive in!

First we need to create two variables in our function. One is the object we will make from the first string and the second is the count of deletions needed that we will return at the end. Then we need to loop through the first string and create an object that assigns each character a number based on how many times it occurs. The code looks like this. We assign each letter in the string as a key in our object and set the number equal to either 1 if that key didn’t previously exist or adding one to the value if it did already exist.

function makeAnagram(a, b) {
  let firstStringObject = {}
  let deletions = 0
  for (let i = 0; i<a.length; i++) {
    let letter = a[i]
    firstStringObject[letter] = (firstStringObject[letter] || 0) + 1
  }
}

Given a word, “mom”, our object would look like {m: 2, o: 1}. Next we need to loop through our second string to compare values. If a value in the string doesn’t exist in the object, we need to make a deletion and therefore add 1 to our deletion count. If the value does exist as a key in our object and the number associated with that key is greater than zero, then we can decrease that number by one, essentially erasing a letter that is the same. Finally if a value exists as a key, meaning it was in the first string, but the value of that key is 0 it means there are no more occurrences left of that letter and therefore we need to add one to our deletions count again.

for (vals of b) {
  if (!firstStringObject[vals]) {
    deletions += 1
  } else if (firstStringObject[vals] > 0) {
    firstStringObject[vals] -= 1
  } else {
    deletions += 1
  }
}

This takes care of our second string, so the only thing left to do is check if there are any letters left in the object we created. If so, we add another one to deletions to account for those letters.

for (const [key, value] of Object.entries(firstStringObject)) {
  if (value > 0) {
    deletions += value
  }
}

Now we have our total count of deletions needed in order to make the strings anagrams of each other, so all that’s left to do is return deletions! This was a revelation for me because I had never considered the option of solving this problem by creating an object that counts occurrences. This approach is much better and faster than the nested loop alternative and has an O(n) time complexity. I think the more I am exposed to these types of problems the more comfortable I will get, but there’s definitely work to do!