Valid Anagram

You are given two strings s and t made of lowercase English letters.

Return true if t is an anagram of s, and false otherwise. Two strings are anagrams when one can be turned into the other by reordering its letters, using every letter exactly as many times as it appears. In other words, every letter must occur the same number of times in both strings.

Example 1

Example 2

Example 3

Constraints

• 1 <= s.length, t.length <= 5 * 104
• s and t consist of lowercase English letters.

Pattern Path · Hashing & Counting · problem 2 of 169

Start simple

Sort both strings and compare them: O(n log n) time; trying every rearrangement would be factorial.

The key idea

An anagram ignores order completely, so the only thing that matters about each string is its multiset of letters: how many a's, how many b's, and so on. Two strings are anagrams exactly when those counts match.

First compare lengths: if they differ, the answer is immediately false. Otherwise count the letters of s in a table, then walk through t and decrement the count of each letter. If a count would drop below zero, t uses that letter more often than s does, so return false.

If the walk finishes, every count is exactly zero: the lengths are equal and no count went negative, so none can be left positive either. With only 26 possible letters the table is a fixed size, which makes the extra space O(1); a hash map works the same way for larger alphabets.

Complexity

• Time: O(n)
• Space: O(1)

Python

from collections import Counter


class Solution:
    def isAnagram(self, s, t):
        if len(s) != len(t):
            return False
        counts = Counter(s)
        for ch in t:
            counts[ch] -= 1
            if counts[ch] < 0:  # t uses this letter more often than s does
                return False
        return True

JavaScript

var isAnagram = function(s, t) {
  if (s.length !== t.length) return false;
  const counts = new Array(26).fill(0);
  const A = 'a'.charCodeAt(0);
  for (let i = 0; i < s.length; i++) counts[s.charCodeAt(i) - A]++;
  for (let i = 0; i < t.length; i++) {
    const k = t.charCodeAt(i) - A;
    counts[k]--;
    if (counts[k] < 0) return false; // t uses this letter more often than s does
  }
  return true;
};

What the interviewer is checking

The interviewer is looking for the counting idea (and the sort-based alternative), plus a discussion of how the answer changes for Unicode or very large alphabets.

Mistakes to avoid

• Comparing only the sets of letters: "aab" and "abb" use the same letters but different counts.
• Forgetting the length check when you only verify that counts never go negative.
• Using a fixed 26-slot array when the input might contain characters outside a to z.

Follow-ups to expect

• What if the strings contain arbitrary Unicode characters? (Use a hash map, not 26 slots.)
• How would you group a list of words into anagram families? (Key each word by sorted letters or counts.)
• How would you find all anagrams of p inside a longer string? (Sliding window of counts.)

In real software

Comparing frequency signatures instead of exact sequences shows up in spell checkers, word games, and checking that two batches contain the same items regardless of order.

Practice next