Valid Anagram

This is problem #2 in NeetCode's Arrays & Hashing section of problems.

Given two strings s and t, return true if the two strings are anagrams of each other, otherwise return false.

An anagram is a string that contains the exact same characters as another string, but the order of the characters can be different.

Example 1:

Input: s = "racecar", t = "carrace"

Output: true

Example 2:

Input: s = "jar", t = "jam"

Output: false

The code is stubbed out as follows:

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:

Doing leetcode style problems as been, for me, a great way to learn that I am not brilliant. But it has revealed to me that I am pretty good at remembering abstract concepts and being able to map them to problems. I share this because I think there's a common misconception that you have to be brilliant to solve leet code problems. You don't. The truth is a lot more painful: you just have to practice them. Practice is slow and frustrating. But it is a good struggle.

With that being said, the solution that I have memorized is fairly simple:

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return sorted(s) == sorted(t)

This was not my insight; I got this from the neetcode site itself.

Let's look at why it works.

If two words are anagrams of each other, then they have the same letters, but in a different order.

carrace and racecar both contain the same letters.

If we sort carrace, we get aaccerr

Likewise, if we sort racecar, we also get aaccerr

Thus, aaccerr == aaccerr evaluates to True only when the two words are anagrams.

There is another interesting solution that is worth looking at at least once:

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        
        letter_ticks = [0] * 26
        a_ord = ord('a')

        for i in range(len(s)):
            letter_ticks[ord(s[i]) - a_ord] += 1
            letter_ticks[ord(t[i]) - a_ord] -= 1
        
        for num in letter_ticks:
            if num > 0:
                return False
        return True

I won't walk through the whole thing line by line. Rather, I'll focus on the key insight. We have an array called letter_ticks that consists of 26 zeros. Why? Well, there's 26 letters in the alphabet. We use a bit of code to map letters to numbers via ord(s[i]) - a_ord. All this does is it takes the ASCII encoding for a letter, such as the letter a with its ASCII encoding of 97, and subtracts the ASCII encoding of 97 from it to give you 0.

This means we can map each letter in the alphabet to an index in our letter_ticks array.

a = 0
b = 1
c = 2
...
x = 23
y = 24
z = 25

If two words are anagrams, then they will increment and decement the exact same elements in the letter_ticks array by the same amount such that the letter_ticks array returns to all zeros.

In the case where s = "racecar" and t = "carrace" the array will change as follows:

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
i = 0
s[0] = 'r'
s[0] = 'c'
[0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]

i = 1
s[0] = 'a'
s[0] = 'a'
[1, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]

# Notice that the first element briefly became 1 and then went back down to 0

i = 2
s[0] = 'c'
s[0] = 'r'
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

# Notice that the letter positions for 'c' and 'r' returned to zero.

As you proceed with this exercise, you realize that if the two words are anagrams, the elements in the array corresponding to the letters in the strings will be incremented and decremented by the same amount, briging every element back to zero by the end of the for-loop.