LeetCode 242 · Arrays & Hashing · concept: hash-maps
Problem
Given two strings s and t, return true if t is an anagram of s — same characters, same counts, any order.
s = "anagram", t = "nagaram" -> true
s = "rat", t = "car" -> false
Approach 1 — sort both
Two strings are anagrams iff their sorted forms are identical.
def isAnagram(s, t):
return sorted(s) == sorted(t)Time O(n log n), space O(n) (sorting builds new lists). Clean one-liner, but the sort is unnecessary work — anagram is about counts, not order.
Approach 2 — count characters (optimal)
Tally each character in s, then spend those tallies down as you walk t. If lengths differ, or any count goes negative / doesn’t reach zero, it’s not an anagram.
def isAnagram(s, t):
if len(s) != len(t):
return False
count = {}
for ch in s:
count[ch] = count.get(ch, 0) + 1
for ch in t:
if ch not in count or count[ch] == 0:
return False
count[ch] -= 1
return TrueTime O(n), space O(1) — space is bounded by the alphabet (≤ 26 for lowercase English, or ≤ 128 ASCII), a constant, not O(n). collections.Counter(s) == Counter(t) is the same logic in one line.
The length short-circuit
if len(s) != len(t): return False isn’t just an optimization — without it, s = "a", t = "ab" would pass the first loop’s checks against the shared prefix and give a wrong answer. Different lengths can never be anagrams, so check it first.
Complexity summary
| Approach | Time | Space |
|---|---|---|
| Sort both | O(n log n) | O(n) |
| Char count | O(n) | O(1) (alphabet-bounded) |
Key insight
Anagram = equal character multisets. The moment a problem is about “same elements, order irrelevant,” a count map (frequency dictionary) is the tool — the single most common hashing pattern in this category. It reappears in Group Anagrams (where the count is the grouping key) and Top K Frequent.
Related
- concept: hash-maps
- prev: Contains Duplicate · next: Two Sum
- Group Anagrams — the count map becomes a bucket key
Software engineering
Infrastructure & security
Computer science
Hardware & engineering