Breaking Down DSAs: Valid Anagram

Since graduating from the Flatiron School two months ago, I've been hard at work learning all I can about data structures and algorithms in preparation for the dreaded technical interview. I found a great collection on LeetCode of the top interview questions and have been slowly making my way through them.

Anybody who's done these kinds of coding challenges knows that there are always multiple approaches and solutions with varying runtimes. I thought it would be helpful to me (and maybe someone else) if I talked through my different solutions to one of the first problems I did, and what I learned along the way. So today I'll be going through a classic question: valid anagram.

The problem is this: given two strings, s and t, write a function to determine if t is an anagram of s. For example, if s = “anagram” and t = “nagaram”, return true. I'll be using JavaScript.

My immediate thought was that if the strings' lengths aren't the same, then there's no way they can be anagrams, and thus we can quickly return false.

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

Obviously, two strings can be the same length but contain different letters, so our function continues. My next (naive) thought was to turn the strings into arrays and sort them.

s = s.split('').sort();
t = t.split('').sort();

Then I could easily compare each letter by iterating through one array and checking it against the other. If the letters aren't the same, return false.

for (let i = 0; i < s.length; i++) {
  if (s[i] != t[i]) {
    return false;
  }
}

If every letter passes this test, then the two strings are confirmed to be anagrams and we can return true! After submitting my solution and feeling pretty smart, LeetCode decided to crush my spirit by telling me that my solution's runtime only beat 47% of other JavaScript submissions.

The great thing about LeetCode is that you see other people's solutions, and thus I fell down a rabbit hole. I discovered what some might call a 'sick one liner' that was similar to what my solution was doing.

return s.split('').sort().join('') == t.split('').sort().join('');

From this solution I learned that my final step of comparing the two arrays using a for loop could be made easier by simply turning the sorted arrays back into strings using .join(). This is because strings can be compared using an equality operator while arrays cannot.

['wow'] == ['wow'];
// returns false;

'wow' == 'wow';
// returns true;

Further research led me to learn quite a bit about optimizing my code's runtime. I learned that using .sort(), while quick and easy to type, is pretty inefficient under the hood. Additionally, in a technical interview, you likely won't be able to use a method that does so much for you.

I then learned a very important lesson about writing efficient functions: objects are king. Objects, or dictionaries in other programming languages, have a constant lookup time, O(1), and thus can be very helpful in optimizing code.

So I set out to try solving this problem again using an object. I determined that I could iterate through one of the strings, using the object to keep track of the number of times each letter appeared. So given the string 'anagram', the object would become:

count = {a: 3, n: 1, g: 1, r: 1, m: 1}

Then I can iterate through the other string, checking first that the letter appears in the object, and if it does, subtracting one from its value. Here's what that looked like:

// create empty object
let count = {};

// iterate through one string, counting letters
for (let i = 0; i < s.length; i++) {
  count[s[i]] = (count[s[i]] || 0) + 1
};

// iterate through other string, checking the object has letter key
for (let i = 0; i < t.length; i++) {
  if (!count[t[i]]) {
    return false
  } else {
    // if letter is in object, subtract count
    count[t[i]] -= 1
  }
}

My solution worked and was faster than 95% of other JavaScript submissions! But there was one final thing I wanted to see if I could refactor. I knew there were other potentially cleaner ways to write my for loops so I did some digging and discovered for...of. I refactored my two for loops and the result was a lot less typing and clearer code!

// original for loop, iterating over the string, checking the object for each letter
for (let i = 0; i < s.length; i++) {
  count[s[i]] = (count[s[i]] || 0) + 1
};

// same loop using for...of syntax
for (letter of s) {
  count[letter] = (count[letter] || 0) + 1
}

I should note that for..of and the similar for...in are newer to JavaScript and thus aren't fully supported everywhere. But for my purposes, it wasn't a problem. So my final function looked like this:

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

  let count = {};

  for (letter of s) {
    count[letter] = (count[letter] || 0) + 1;
  }

  for (letter of t) {
    if (!count[letter]) {
      return false;
    } else {
      count[letter] -= 1;
    }
  }
  return true;
};

And that's all folks! I had a great time refactoring and learned a lot along the way. Catch you next week!