Anagram Fun

Image via Wikipedia

A while back I wrote a short post on how to detect if two strings were an anagram, you can find it HERE. This past week I was invited to take a code challenge from Facebook and it took this issue one step further. The code challenge was hosted through HackerRank and the problem was called Fun with Anagrams. I thought exploring this might be of some use to you all out there. First, let’s state out the problem. (Quick note: After completing the challenge I was not able to access it again. Hence, the following problem was recreated from memory and may differ slightly from the original but the gist is the same.)

Real quick…what is an anagram? An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once (Wikipedia). We are going to expand this to be any combination of letters regardless if they form actual words.

If you are given an array of strings, determine if any of them are anagrams then remove any of the subsequent anagrams. Return an array of the first instance of each anagram that is sorted in descending order.

Constraints:

1. Input array will only contain strings that consist of lowercase letters a-z.
2. 0 < array.length < 1000

Example:

1. Input: [‘anagram’, ‘farmer’, ‘dog’, ‘granmaa’, ‘reframe’, ‘framer’, ‘god’]
2. Anagrams: (‘anagram’, ‘granmaa’) (‘farmer’, ‘framer’) (‘dog’, ‘god’)
3. Remove the subsequent anagrams and keep original. Final output: [‘anagram’, ‘dog’, ‘farmer’, ‘reframe’ ]

Now that the problem is presented, the next step would be to break it down into simpler tasks. Let’s look at this process then write it out before coding anything.

Tasks:

1. Compare strings to determine if they are anagrams.
2. If anagrams are found, remove the second instance.
3. If a string is not an anagram with any other string in the array, it remains in the array.
4. Sort remaining array.

Looking back over my first post on anagrams, task #1 here can be broken down further. Here is an updated task list.

1. Convert string into a comparable format.
2. Compare each string against the following strings in the array.
3. If any anagrams are found, remove the subsequent strings.
4. If a string is not an anagram with any other string in the array, it remains in the array.
5. Sort the strings remaining in the array.

With this list of tasks we can begin to write some code. I would determine that the first couple tasks might be best as helper functions. Helper functions are functions that accomplish simpler tasks that can be reused throughout the code. For this problem we are going to write a couple helper functions that our main function can call when needed. This helps keep the code cleaner and can serve the DRY principle.

Task #1

Before we can compare two strings to see if they are anagrams, each string must be converted into a similar format. In my first post I demonstrated two possible ways to do this. The first was to convert each string to an object and then to compare each objects properties. This was a bit cumbersome so I also showed that by manipulating each string we can then determine equality. Let’s look at that again.

Here the convertStr function takes in a string and defines a variable ‘text’. ‘Text’ is defined as the array created by calling .split(‘’) on the input string. This method takes the string and splits it into individual strings made up of one character each and returns them in an array. Then, by calling .sort() on that array all the strings are sorted in descending order, in this case alphabetically. Finally, a new variable ‘newText’ is defined by calling .join(‘’) on that array which joins all individual strings in an array into one string. This function then returns that new string. Thanks to the chaining property of array methods we can clean this up a bit.

Much better!

Task #2

Once the strings have been converted to an alphabetized list of letters, it is easy to compare them. Let’s think again about the definition of an anagram and how we are using it. If you have a base string of letters an anagram would be any rearranged combination of those same letters, keeping the length the same and using each letter the same number of times. So if we take our base string and convert it to an alphabetized string of characters it would stand to reason that any anagram of that base string would convert to an identical alphabetized string. If the converted strings are identical then the comparison helper function should return ‘true’.

I used a ternary here because I like them, you could use an if/else statement as well.

Task #3 & 4

The next tasks are going to make use of the helper functions. Let’s code out the main function step by step.

Starting out, we declare the function ‘funWithAnagrams’ and have it take in an array as an argument. That original array will be altered through this process so we can return the same variable name. Next we code a standard for loop. Inside that for loop we put…

…another for loop. This step allows us to have two incrementing variables (i, j). Now as we loop through the array we do a second loop through the rest of the array. What to do with these loops?

Inside the second for loop an if statement is used. In the if statement we call the helper function ‘compare’. The first argument passed in is the string being used as the base and is called by its index number represented as ‘i’. The second string is to be compared to the base and is called by its index number represented as ‘j’. The ‘j’ index number is initially set as the index number directly following ‘i’. The ‘j’ index number is incremented up by one until it is one less than the length of the initial array. By using the second for loop the function is able to cycle through each increment of ‘j’ before incrementing ‘i’.

Now that was confusing. What all of that basically says is that the function will move through the array one string at a time while checking that one string against all of the remaining strings. That leaves us with the question, what is the if statement doing. In the if statement the “compare” function is called and if it returns true then the .splice() method is called to remove the indexed string. The .splice() method returns the modified original string.

Task #5

So far the ‘funWithAnagrams’ function has taken in an array, used two for loops to iterate through that array, and removed any strings from that array that are anagrams of preceding strings. The last requirement is that the function return the array sorted. Easy enough!

There it is, a solution to the Facebook code challenge question Fun with Anagrams. Notice I said ‘a’ solution. Every problem has many different ways to solve them. This solution is just one of them, but it is not the most efficient. Can you come up with a more efficient one? Good luck out there.

Please note: Again I want to mention that this problem is from memory and may not be the exact problem poised by either Facebook or HackerRank. If you would like to find out, apply to Facebook HERE.