4.4.2 — Valid Anagram

LeetCode 242 · Easy · ★ Blind 75

The problem

Return true if t is a rearrangement of s — the same letters, the same number of each.

s = "anagram", t = "nagaram"   →  true
s = "rat",     t = "car"       →  false
s = "aacc",    t = "ccac"      →  false

That last one matters. Both strings use only a and c, so checking which letters appear says true. The right answer is false. An anagram is about counts, not membership.

Up to 50,000 characters, all lowercase English letters.

The pattern

Two strings are anagrams when they have the same letter counts. So count the letters in each and compare.

Sorting both strings and comparing also works, and it is a fine first answer. But sorting puts the letters in order, and the question only asks how many there are. Ordering is more work than counting, so a linear solution must exist.

The solution

Add one for each letter of s, subtract one for each letter of t. If they are anagrams, every count ends at zero.

Python

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

        count = [0] * 26
        for i in range(len(s)):
            count[ord(s[i]) - ord('a')] += 1
            count[ord(t[i]) - ord('a')] -= 1

        return all(c == 0 for c in count)

TypeScript

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

  const count = new Array(26).fill(0);
  const a = 'a'.charCodeAt(0);
  for (let i = 0; i < s.length; i++) {
    count[s.charCodeAt(i) - a]++;
    count[t.charCodeAt(i) - a]--;
  }

  return count.every(c => c === 0);
}

Three things worth naming.

The length check does two jobs. It rejects obvious mismatches early, and it makes it legal to walk both strings in one loop. Without it you would need two loops.

ord(c) - ord('a') turns a letter into a slot number. ord('c') is 99 and ord('a') is 97, so c lands in slot 2. You will use this conversion constantly.

The counts cancel. A count left positive means s used a letter more often than t. Negative means the reverse. Both are wrong, and both are caught by the same "is it zero" test, so one array is enough.

Complexity

O(n) time. O(1) space — 26 integers, whatever the string length.

The O(1) claim depends on the alphabet being fixed at 26. Say that out loud when you claim it. With an arbitrary alphabet you use a map instead, and the space becomes O(k) for k distinct characters:

from collections import Counter
return len(s) == len(t) and Counter(s) == Counter(t)

The Unicode follow-up

This gets asked every time.

The 26-slot array is gone, because Unicode has over 150,000 characters. Use a map.

.length also stops meaning what you expect. In JavaScript a string is a sequence of UTF-16 code units, so "😀".length is 2 and s[i] can hand you half an emoji. Iterate with for (const ch of s), which is code-point aware. Python 3 counts code points already, so len("😀") is 1.

Where this goes next

• Group Anagrams — the same counts used as a map key. That is 4.4.4.
• Find All Anagrams in a String and Permutation in String — keep this count array for a window, adding the character entering on the right and removing the one leaving on the left. 4.6.

The through-line is character counts, maintained as you move. Once you can do that, a whole family of string problems collapses into one technique.

Next: 4.4.3 Two Sum — the most famous problem on the list, and the third use of a hash map: storing what you still need.