Valid Anagram | LeetCode 242 – Terrible Whiteboard

The function in this question needs to determine if two strings are anagrams. Strings are anagrams if you can use the letters in one string to form the other string (in this case, each letter can be used only once). For example, map is an anagram of pam, angle is an anagram of angel, and gallery is an anagram of largely.

The key to solving this problem is realizing that you don’t need to compare every permutation of the second string to the first. All you really need to do is check if the letter counts are the same. Going back to the examples above, we know
– map and pam are anagrams because they both have 1 p, 1 a, and 1 m
– angle is an anagram of angel because they both have 1 a, 1 n, 1 g, 1 l and 1 e
– gallery is an anagram of largely because they both have 1 g, 1 a, 2 ls, 1 e, 1 r, and 1 y.

Now, to the code. Let’s start with the function skeleton provided by LeetCode.

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function(s, t) {}

As we can see, the function expects two string arguments. These will be compared against each other to determine if they are anagrams.

First off, we know that to be considered anagrams, the strings must be the same length. So right off the bat, we can return false if their lengths differ.

if (s.length !== t.length) {
  return false;
}

Now we need to keep track of the letter counts in the first word. We can do this using an object data structure.

let letterCount = {};

The key will be the letter and the value will be the count of that letter. The word “gallery” will look like this. The letter is on the left and its count is on the right (this is not code, just something you can visualize):
– g: 1
– a: 1
– l: 2
– e: 1
– r: 1
– y: 1

To add the letters and their respective counts, we can loop over every letter in the first word. If the letter already exists in the letterCount object, we will increment (add 1 to) the count. For example, if we come across the letter “l” and it is already in the letterCount object with a count of 1, we increment it, which would give it a count of 2 since this is the second time we’re seeing it. Otherwise, we add the letter with a respective count of 1 to the letterCount object.

for (let letter of s) {
  if (letterCount[letter]) {
    letterCount[letter]++;
  } else {
    letterCount[letter] = 1;
  }
}

Let’s review what we’ve done so far. We’ve checked if the strings are the same length. If they are not, we can immediately return false since they cannot be anagrams if they have different lengths. Then we looped over every letter in the first word (the key) and added its count to an object (the value) we named letterCount.

Now we need to compare the letters in the second word to the letters and their counts in the first word. If a letter in the second word does not appear in the first word, we can return false because we know that every letter in the second word has to be in the first word if they are anagrams. If a letter in the second word does appear in the first word, we need to check the count of it and make sure it’s not less than 1. Why? Because, remember, the letter count in the second word has to be the same as the letter count in the first word. If we’re subtracting more (for example) letter “l”s from the first word than the first word even has, it means the second word has more letter “l”s than the first word, making it not an anagram.

But if it is at least 1, we decrement (subtract 1 from) its corresponding count.

If that’s confusing, picture it like this. Referring to the word gallery from above, the letter count in the letterObject would be:
– g: 1
– a: 1
– l: 2
– e: 1
– r: 1
– y: 1

If we want to know if the word “galas” is its anagram (besides the fact that their lengths are different), here is what that would look like.

We start with the letter “g” in gala and compare it to the letters counts in the word “gallery” (see above). The word “gallery” has a count of 1 “g”. When we subtract 1 from that count, we get the number 0, which is fine. It means at this point, the two words have the same number of “g”s. The letter counts now look like this:

– g: 0
– a: 1
– l: 2
– e: 1
– r: 1
– y: 1

Now we move on to the next letter in galas, “a”. As we see above, the letterCount object shows a count of 1 for the letter “a”. That’s good. We can subtract 1 from that, bringing the “a” count to 0.

– g: 0
– a: 0
– l: 2
– e: 1
– r: 1
– y: 1

Next comes the letter “l” in galas. We look at the letterCount object and see a count of 2. Good. We can subtract 1 from that.

– g: 0
– a: 0
– l: 1
– e: 1
– r: 1
– y: 1

Now comes the second letter “a”. We can’t subtract 1 from the letterCount above because there are zero “a”s left in the letterCount object.

– g: 0
– a: 0
– l: 1
– e: 1
– r: 1
– y: 1

This means that “galas” has at least one more “a” than gallery, meaning they are not anagrams. We can return false immediately. We don’t even need to look at its final letter, “s”.

Here is what that part of the function looks like in code:

for (let letter of t) {
  if (letterCount[letter] === undefined) {
    return false;
  }

  if (letterCount[letter] < 1) {
    return false;
  }

  letterCount[letter]--;
}

Now let’s step away from the gallery/gala example and continue writing the function. If we’ve managed to get to this part of the code without returning false, it means the two words are the same length and the counts of their letter counts as the same. That means they are anagrams! All we have do do now is return true (true means they are anagrams, false means they are not), and we’re done.

return true;

And that’s it! The full implementation is at the bottom of this page, but if you want to support us and are interested in the resources we use to make this content, check out the links below.

AFFILIATE LINKS

Great resource I use to learn algorithms:
40% off Tech Interview Pro: http://techinterviewpro.com/terriblewhiteboard
20% off CoderPro: http://coderpro.com/terriblewhiteboard

Last, but not least, here is the full implementation.

var isAnagram = function(s, t) {
  if (s.length !== t.length) {
    return false;
  }  

  let letterCount = {};

  for (let letter of s) {
    if (letterCount[letter]) {
      letterCount[letter]++;
    } else {
      letterCount[letter] = 1;
    }
  }

  for (let letter of t) {
    if (letterCount[letter] === undefined) {
      return false;
    }

    if (letterCount[letter] < 1) {
      return false;
    }

    letterCount[letter]--;
  }

  return true;
};

Link to problem on LeetCode: https://leetcode.com/problems/valid-anagram/