Valid Anagram — InterviewPrepKit

Solving tips

When 'rearrangement doesn't matter,' compare frequency signatures, not sequences.
Tally 26 letter counts (increment for s, decrement for t in one combined pass) and require all counters to be zero; O(n) time, O(1) space.
Sorting both strings and comparing works too (O(n log n)) but the interviewer usually wants the O(n) counting argument; for the Unicode follow-up swap the fixed array for Counter.
Pitfall: check len(s)==len(t) first when using zip (it truncates to the shorter string), and never compare set(s)==set(t), which drops multiplicity.

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

Hint 1

Two strings are anagrams exactly when some canonical form of each is identical. What canonical form ignores letter order?

Hint 2

Sorting works but costs O(n log n). Order doesn't actually matter — only how many times each letter appears. Can you compare that directly?

Hint 3

Count the 26 letter frequencies of each string (an array of 26 ints, or a `Counter`) and compare the two tallies — one pass over each string.

TL;DR

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

Approach 1 — Brute force

For each character of s, hunt for a matching character in a mutable copy of t and cross it off; if any character can’t be matched, or letters remain in t, the strings aren’t anagrams.

class Solution:
    def isAnagram(self, 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

The insight: an anagram is just a reordering, so sorting both strings maps every anagram class to a single canonical string — then one equality check settles it.

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

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

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

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

Approach 3 — Frequency count

The insight: 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 land on zero.

class Solution:
    def isAnagram(self, 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":

Lengths match (3 and 3), continue.
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.
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


class Solution:
    def isAnagram(self, 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.
Reaching for the sort out of habit in a follow-up discussion: it’s correct, but the interviewer is usually fishing for the O(n) counting argument.

Pattern takeaway

When a problem says “rearrangement doesn’t matter”, the object you should compare is the frequency signature, 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.