Data Structures: Anagram Problem Solution

Key Takeaways

Hi, I'm Gail Lock McDow, author of Cracking the Coding Interview. Today I'm going to solve a problem called making anagrams. This problem goes as follows. You have two strings just with the lowercase characters A to Z. How many characters would you have to remove from the two strings to make them anagrams? So anagrams, as you might remember, are just permutations of a word. So rearrangements of the words. So for two words to be anagrams, it means that they have the same characters but just in different orders. So for example, you have the input hello and billion. You'd have to remove six characters total. The H and the E from hello and the B, I I N from billion. And then that will leave you with L, L, and O in each of the two strings. So given two arbitrary strings, how many characters would you have to remove from each string to make them anagrams? Well, anagrams are mean that they have the same exact characters and the same number of each characters. So without the order mattering. So if you want to know, you know, if you want, you have just the string a a and a and you want to make those two things anagrams of each other, you'd have to remove two a's from the first string. So if we have a whole bunch of characters, it's the same process essentially. If we want to make two strings anagrams each other, count how many times each character appears in each string and then look at the difference between those values. So let's turn to the code now. So I already have a main function written um that handles my input. So now I just need to write this function. Okay, what this what the logic here is going to be is just count how many times each character appears. So I'm going to and then get the del delta between these. So int char count one um is going to be I'll just push this off another function. I'm not going to write it right now. Um, get char counts of first. Then I do basically the same thing for the second string. And then I return the delta between these. Okay. So note here that I've been pretty aggressive with modularization. That's kind of a good thing to do in order to show great coding style. Okay, now let's turn to how getchar works. Get char counts works. So that's going to take in a string. I'll just call it s. And it's going to create. So it's going to need an array that with one slot for each letter. So I'm going to call this char counts. And it's going to be a size number of letters. And then it's going to go through each string, each character. Um, so for into i equals zero, i less than s.length oops i ++ char c equals um s.char i and then I need to convert like a to zero, b to one, c to two, etc. So one way of doing that is I get the offset. So I can take the character A and convert that to its ASKI code. Um then the character B will be the next integer. So in Java we can kind of treat integers treat characters sort of as integers. And so giving doing this we'll get the character value of A. So if I do B minus A, I'd actually get one. So the code here is going to be this character C minus this offset. And then so that's going to give me like A to 0, B to 1, C to 2, etc. Then I just need to increment the value of that code and return that array. My final method is this get delta function and it's going to take in two strings or two arrays and compute the delta between each value. Um so I'll do some very basic error handling right now. Um, in ideal world I should probably, you know, create throw an exceptional that, but I'm just going to give it a negative one. So, the rays need to be the same length. Uh, okay. Now, I just need to walk through each value in the arrays and compute the absolute value of their differences. So math.absolute value of array of one of i minus array two of i and delta plus equals difference turn delta. Okay. Now let's see how this works. I'll run this. All right. We pass our test cases. That's fantastic. I'll try a slightly more advanced one. And it looks like we're doing great. So let's review how our code works. So we have this number needed function and it counts how many times the character appears in each string and then it walks through the two counts and compute the difference of it. So to get the number of characters in each string that's pretty easy. We just use a simple uh array will be sufficient here. If we had a bigger variety of strings um or characters, some other slightly different data set, we might want to use a hashmap instead. A simple integer array is sufficient here. And then we walk through and get the delta between each value in each array. Now, we need to know again that it's the same length. So that's, you know, this is a pretty straightforward problem. One tip that's useful in a lot of problems and it was useful here is to really define and think about what exactly does it take to make two things anagrams and the algorithm sort of follows from that explanation. So keep that in mind for your future problems. Good luck.