Valid Anagram
Decide whether two strings use exactly the same letters, by counting rather than sorting
Problem Statement
Given two strings s and t, return true if t is an anagram of s — that is, if t uses exactly the same letters with exactly the same multiplicities.
Input: s = "anagram", t = "nagaram"
Output: true
Input: s = "rat", t = "car"
Output: falseIntuition
Anagrams are strings that differ only in the order of their characters. So any comparison that ignores order will do.
Two canonical forms
Sort both strings — "anagram" and "nagaram" both sort to "aaagmnr". If the sorted forms are equal, they are anagrams. Simple, O(n log n).
Count the characters — build {a: 3, n: 1, g: 1, r: 1, m: 1} for each string and compare the maps. O(n), which is strictly better.
The counting version has one more refinement worth knowing: instead of building two maps and comparing them, build one map by incrementing for s and decrementing for t. If the strings are anagrams, every count cancels to zero.
The single-map trick
s = "rat", t = "car"
+ 'r' → {r: 1}
+ 'a' → {r: 1, a: 1}
+ 't' → {r: 1, a: 1, t: 1}
- 'c' → {r: 1, a: 1, t: 1, c: -1}
- 'a' → {r: 1, a: 0, t: 1, c: -1}
- 'r' → {r: 0, a: 0, t: 1, c: -1}
Not all zero → not anagrams.Watch it run
Approach
Compare lengths first
Different lengths can never be anagrams, and this O(1) check saves the whole count.
Count characters of t, decrementing
Returning false the moment a count goes negative gives an early exit.
Solution
from collections import Counter
def is_anagram(s: str, t: str) -> bool:
"""True if t uses exactly the same letters as s."""
if len(s) != len(t):
return False
counts: dict[str, int] = {}
for char in s:
counts[char] = counts.get(char, 0) + 1
for char in t:
if char not in counts:
return False
counts[char] -= 1
if counts[char] < 0:
return False # t has more of this letter than s
return TrueUsing the standard library, which does the same thing:
def is_anagram_counter(s: str, t: str) -> bool:
return Counter(s) == Counter(t)
def is_anagram_sorted(s: str, t: str) -> bool:
return sorted(s) == sorted(t)Why the length check makes the final scan unnecessary
If the lengths are equal and no count ever goes negative, then no count can be left positive either — the total increments and decrements are the same number. So the second loop finishing without a negative is the proof, and there is no need to iterate the map at the end.
Without the length check, s = "aab", t = "ab" would pass the loop with a leftover {a: 1} and wrongly return true.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(k)
- Time — two passes over strings of length
n, withO(1)map operations. The sorting version isO(n log n). - Space —
O(k)wherekis the alphabet size. For lowercase English that is at most 26, effectivelyO(1).
The fixed-array variant
When the input is guaranteed lowercase a–z, a 26-element integer array replaces the hash map and is measurably faster — array indexing beats hashing. The follow-up question "what if the input contains Unicode?" is exactly why the hash map version is the more general answer.
Edge Cases
Related Problems
- Group Anagrams — the many-strings version of the same canonical-form idea
- Isomorphic Strings — structure matching rather than multiset matching
- Number of Good Pairs — another problem solved purely by counting