Valid Anagram

Problem

Given two strings s and t, return True if t is an anagram of s — that is, if t can be formed by rearranging the letters of s, using every letter exactly once — and False otherwise.

Examples

• s = "anagram", t = "nagaram" → True — same letters, same multiplicities (3×a, 1 each of n, g, r, m).
• s = "rat", t = "car" → False — t contains a c that s doesn’t have.
• s = "ab", t = "abb" → False — different lengths can never be anagrams.

Constraints

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

Follow-up: what would you change if the inputs could contain any Unicode characters?

Think about it first

TL;DR

Compare letter-frequency counts — O(n) time, O(1) space (26-letter alphabet).

Approach 1 — Brute force

For each character of s, search a mutable copy of t for a matching character and remove it. If any character cannot be matched, or letters remain in t at the end, the strings are not anagrams.

def isAnagram(s: str, t: str) -> bool:
    remaining = list(t)
    for ch in s:
        if ch in remaining:
            remaining.remove(ch)
        else:
            return False
    return not remaining

Complexity: O(n²) time (in and remove each scan the list), O(n) space.

At n = 5 * 10^4 that’s ~2.5·10^9 character comparisons in the worst case — far too slow.

Approach 2 — Sort both strings

An anagram is a reordering, so sorting both strings maps every anagram class to a single canonical string, and one equality check decides the result.

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

Walkthrough on s = "anagram", t = "nagaram":

1. sorted(s) → ['a', 'a', 'a', 'g', 'm', 'n', 'r'].
2. sorted(t) → ['a', 'a', 'a', 'g', 'm', 'n', 'r'].
3. The lists are equal → True.

Complexity: O(n log n) time, O(n) space for the sorted copies.

Approach 3 — Frequency count

Order is irrelevant; only how many of each letter each string has matters. Tally both strings into 26 counters and compare, or equivalently increment for s and decrement for t in one combined pass and require every counter to end at zero.

def isAnagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    counts = [0] * 26
    base = ord("a")
    for a, b in zip(s, t):
        counts[ord(a) - base] += 1
        counts[ord(b) - base] -= 1
    return all(c == 0 for c in counts)

Walkthrough on s = "rat", t = "car":

1. Lengths match (3 and 3), continue.
2. Pair ('r', 'c'): counts → r:+1, c:−1. Pair ('a', 'a'): a goes +1 then −1, net 0. Pair ('t', 'r'): t:+1, r back to 0.
3. Final nonzero counters: c = −1, t = +1 → not all zero → False. The −1 on c is exactly the letter t has that s lacks.

Complexity: O(n) time, O(1) space — the counter array is a fixed 26 slots regardless of input size.

For the Unicode follow-up, swap the fixed array for collections.Counter (a hash map), since the alphabet is no longer small and dense:

from collections import Counter


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

This stays O(n) time but uses O(k) space for k distinct characters.

Common pitfalls

• Forgetting the length check when using the single-pass increment/decrement version with zip — zip silently truncates to the shorter string, so "ab" vs "abb" would wrongly pass without it.
• Comparing set(s) == set(t) — sets discard multiplicity, so "aab" and "abb" would wrongly match.
• Defaulting to the sort in a follow-up discussion: it is correct, but the interviewer is usually looking for the O(n) counting argument.

Pattern takeaway

When a problem says rearrangement does not matter, compare the frequency counts, not the sequence. A fixed-alphabet count array (or a Counter for open alphabets) turns any anagram-style equivalence into an O(n) tally-and-compare.