LeetCode Meditations: Valid Anagram

For this one, let's start with the description:

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

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.

And, both arguments will consist of lowercase English letters.

For example:

isAnagram('anagram', 'nagaram');
// -> true

isAnagram('rat', 'car');
// -> false

Here, we can use Map to store the letter counts in both strings. If the same letter in the second string doesn't occur the same number of times as in the first string, we know that they are not anagrams.

Of course, the first thing to check is if the lengths of the strings are equal, because if they are not, then there is no way they are anagrams in the first place.

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

  let isValid = true;

  let sDict = new Map();
  let tDict = new Map();

  // Initialize the objects with letters mapping to letter counts 
  for (const letter of s) {
    const letterCount = sDict.get(letter);
    !letterCount ? sDict.set(letter, 1) : sDict.set(letter, letterCount + 1);
  }

  for (const letter of t) {
    const letterCount = tDict.get(letter);
    !letterCount ? tDict.set(letter, 1) : tDict.set(letter, letterCount + 1);
  }

  // Check if a letter doesn't occur the same number of times
  sDict.forEach((letterCount, letter) => {
    if (tDict.get(letter) !== letterCount) {
      isValid = false;
    }
  });

  return isValid;
};

Time and space complexity

My guess for the time complexity is $O(n)$ as we iterate through the string's length to create the map. Space complexity would be $O(n)$ as well, because creating the map grows linearly as the length of the string increases.

Using Python

Many things are potential one-liners in Python, so

collections.Counter(s) == collections.Counter(t)

is the easiest thing to do.

But to recreate the above code, it might look like this:

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False

        s_dict = {}
        t_dict = {}

        for letter in s:
            s_dict[letter] = s_dict.get(letter, 0) + 1

        for letter in t:
            t_dict[letter] = t_dict.get(letter, 0) + 1

        for letter, letter_count in s_dict.items():
            if t_dict.get(letter, 0) != letter_count:
                return False

        return True

Note that we don't need an isValid flag in this case, as we're not checking the letter counts inside a function with limited scope inside some function like a forEach.

Also inside the last loop, as the letter in s_dict may not be in t_dict, we're using t_dict.get(letter, 0), so if it doesn't exist, it would be initialized with the count 0.
I don't think that's a good solution at all, though.
So let's take a deep breath, and look at NeetCode's solution.

NeetCode's solution was pretty similar to the Python version above.

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False

        countS, countT = {}, {}

        for i in range(len(s)):
            countS[s[i]] = 1 + countS.get(s[i], 0)
            countT[t[i]] = 1 + countT.get(t[i], 0)

        for c in countS:
            if countS[c] != countT.get(c, 0):
                return False

        return True

The time and space complexity in this case are $O(n)$ as well.

To get rid of the extra memory usage and make the space complexity $O(1)$ , he mentions the solution where you can compare the sorted versions of the strings:

sorted(s) == sorted(t)

In the case of TypeScript (or JavaScript) it could be:

[...s].sort().join('') === [...t].sort().join('');

But, of course, sorting algorithms can't get better than $O(n \ log \ n)$ when it comes to time complexity, and some of them use $O(n)$ space to create additional storage as well, so it's another trade-off.

We can take one more deep breath now.

Next up is Two Sum, until then, happy coding.