242 - Valid Anagram

Difficulty: Easy | Pattern: Hash Map / Counting | Company tags: Amazon, Google, Facebook, Microsoft

Problem Statement

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, using all the original letters exactly once.

Example 1:

Input: s = "anagram", t = "nagaram"
Output: true

Example 2:

Input: s = "rat", t = "car"
Output: false

Constraints: 1 <= s.length, t.length <= 5 * 10^4; s and t consist of lowercase English letters.

Follow-up: What if the inputs contain Unicode characters? How would you adapt your solution?

Approach 1: Character Counting (Hash Map)

Key insight: Two strings are anagrams if and only if they have the same character frequency. Count characters in s, then subtract counts for t. If all counts are zero at the end, they are anagrams.

from collections import Counter

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

Or manually with a dictionary:

def isAnagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    
    count = {}
    for c in s:
        count[c] = count.get(c, 0) + 1
    for c in t:
        count[c] = count.get(c, 0) - 1
        if count[c] < 0:
            return False
    return True

Approach 2: Array (ASCII optimization)

For lowercase English letters only, use a fixed-size array of 26 instead of a hash map — faster constant factors:

def isAnagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    
    count = [0] * 26
    for c in s:
        count[ord(c) - ord('a')] += 1
    for c in t:
        count[ord(c) - ord('a')] -= 1
    
    return all(x == 0 for x in count)

Approach 3: Sorting

Sort both strings and compare. Simple but O(n log n):

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

Algorithm Flow

Dry Run

s = "anagram", t = "nagaram"

After counting s: {a:3, n:1, g:1, r:1, m:1} After subtracting t: {a:3-3=0, n:1-1=0, g:1-1=0, r:1-1=0, m:1-1=0} All zeros → True ✓

Follow-up: Unicode Characters

The array approach (fixed 26-element array) only works for lowercase ASCII. For Unicode, use a Counter or dictionary — the key space is unbounded, but the hash map handles it naturally.

Edge Cases

• Different lengths → always False (quick O(1) check before any counting)
• Empty strings s = "", t = "" → True (both length 0)
• Same string → True (trivially an anagram of itself)
• One character each: s = "a", t = "b" → False

Complexity

Approach	Time	Space
Counter / Hash map	O(n)	O(1)* or O(k) for Unicode
Array (26 chars)	O(n)	O(1)
Sorting	O(n log n)	O(n)

*Space is O(1) for lowercase ASCII since the alphabet is bounded at 26 characters.

Key Terms

Term	Definition
Hash map counting	Storing character frequencies in a dictionary keyed by character, incrementing/decrementing as characters are processed.
Fixed-size array	A 26-slot array used instead of a hash map when the alphabet is bounded (lowercase a-z), avoiding hashing overhead.
Frequency signature	The multiset of character counts that uniquely identifies whether two strings contain the same letters.
Early exit	Checking len(s) != len(t) first to avoid unnecessary O(n) work when strings can't possibly be anagrams.
Comparison sort	Sorting both strings and comparing them character-by-character as an alternative correctness check.

FAQ

1. Can this be solved without extra space? Not truly O(1) in the general case — the array approach uses O(1) additional space only because the alphabet size (26) is a constant, not because no space is used.
2. What if the input is empty? Two empty strings are anagrams of each other (isAnagram("", "") returns True) since both have zero length and identical (empty) frequency counts.
3. How would this change if the strings could contain Unicode characters? Replace the fixed 26-element array with a hash map (Counter or dict), since the key space is no longer small and bounded.
4. What's the follow-up interviewers usually ask? How to handle Unicode input, and how to solve "Group Anagrams" (LC 49), which generalizes this idea to many strings at once using the frequency signature as a hash key.
5. Why check lengths before counting? It's an O(1) check that eliminates the majority of non-anagram cases instantly, avoiding a full O(n) pass when it's not needed.

Quick Revision

• Two strings are anagrams if and only if they have identical character frequency counts.
• First check len(s) != len(t) — different lengths can never be anagrams.
• Build one frequency count from s, then decrement it while scanning t.
• If any count goes negative during the t scan, return False early.
• All counts ending at zero (or an empty dict after Counter subtraction) confirms an anagram.
• For lowercase-only inputs, use a 26-element array indexed by ord(c) - ord('a') for speed.
• For Unicode or larger alphabets, use a hash map instead of a fixed array.
• Sorting both strings and comparing is a simpler O(n log n) alternative, useful if array/hash map isn't allowed.
• Time complexity: O(n) for counting approaches, O(n log n) for sorting.
• Space complexity: O(1) for bounded alphabets, O(k) for k distinct Unicode characters.

Related Problems

• Group Anagrams (LC 49) — uses the same frequency-signature idea as a hash map key to group multiple strings.
• Find All Anagrams in a String (LC 438) — combines anagram frequency counting with a sliding window.
• Ransom Note (LC 383) — same character-counting pattern applied to a one-directional "can be built from" check.