Valid Anagram (LeetCode 242)

The problem

You get two strings s and t. Return True if t is an anagram of s, meaning it uses exactly the same characters, the same number of times, in any order. Otherwise return False.

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

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

Both of the first pair have three as and one each of n, g, r, m. "rat" has a t and "car" has a c, so they differ.

How to think about it

Start with brute force. For each character of s, find and remove a matching character from t. Each search is O(n), so that’s O(n²). A better first idea is to sort both strings and compare: anagrams sort to the same string. That is O(n log n) and very short to write: sorted(s) == sorted(t).

The key insight: an anagram is defined by counts, not order. Two strings are anagrams if and only if every character appears the same number of times in both. So build a frequency table for each string and compare the tables. Building a table is one O(n) pass; comparing two tables is O(number of distinct characters).

In Python, Counter is that frequency table. Counter("anagram") is a dictionary {'a': 3, 'n': 1, 'g': 1, 'r': 1, 'm': 1}, and two Counters compare equal when they have the same keys with the same counts. Different lengths automatically give different counts, so you don’t need a separate length check.

Which pattern is this? Hash map frequency counting. The tell is “same letters, any order”, or “rearrangement of”.

Approach

1. Count the characters of s into a frequency map.
2. Count the characters of t into another.
3. Return whether the two maps are equal.

If you can’t use Counter, do it with one array of 26 zeros: add one for each character of s, subtract one for each of t, and check that every entry is zero at the end.

Solution

from collections import Counter

def is_anagram(s, t):
    return Counter(s) == Counter(t)     # same characters with the same counts
# is_anagram("anagram", "nagaram") -> True

Dry run

On s = "anagram", t = "nagaram":

Every count matches, so it returns True. For "rat" and "car", t appears in only the first Counter and c only in the second, so it returns False.

Complexity

• Time: O(n). Each Counter is one pass over its string, and comparing them is O(k) for k distinct characters.
• Space: O(1) for lowercase English letters, since each table holds at most 26 keys. For general Unicode input it’s O(k).

Edge cases and pitfalls

• Different lengths: "a" vs "aa" gives counts {a: 1} and {a: 2}, so it returns False with no extra check.
• Empty strings: two empty Counters are equal, so is_anagram("", "") is True.
• Case and spaces: "Listen" and "silent" differ because L is not l. Normalise first if the problem says to.
• Using a set (set(s) == set(t)) ignores counts. "aab" and "abb" would wrongly pass.
• Unicode follow-up: Counter already handles any character. The 26-slot array version does not.

Related problems

• Group Anagrams (LeetCode 49): use a canonical form of each word as a dictionary key.
• Ransom Note (LeetCode 383): one count table must “fit inside” the other instead of being equal.
• Find All Anagrams in a String (LeetCode 438): compare counts inside a sliding window.