Valid Anagram
Understand the problem
Given two strings s and t, return true if t is an anagram of s — that is, t can be formed by rearranging all the characters of s.
Example:
s = "anagram", t = "nagaram"
output = true // same characters, different order
s = "rat", t = "car"
output = false // 'r','a','t' ≠ 'c','a','r'Assumption: only lowercase English letters (a-z).
Two anagrams must have the same length.
Show the basic approach (slower)
O(n log n) time, O(n) spacefunction isAnagram(s: string, t: string): boolean {
if (s.length !== t.length) return false
// Sort both strings, then compare
return s.split('').sort().join('') === t.split('').sort().join('')
}Sorting a string of length n costs O(n log n).
Simple, but slower than necessary — a hash map does it in O(n).
Optimal solution
O(n) time, O(1) spacefunction isAnagram(s: string, t: string): boolean {
if (s.length !== t.length) return false
const count = new Map<string, number>()
// Count character frequencies in s
for (const ch of s) count.set(ch, (count.get(ch) ?? 0) + 1)
// Subtract frequencies using t
for (const ch of t) {
const freq = count.get(ch)
if (!freq) return false // char missing from s or already used up
count.set(ch, freq - 1)
}
return true
}This is the optimal approach: count the character frequencies of s in a hash map, then "consume" them one character at a time with t.
- If any character is missing or already at 0 → not an anagram.
- Space is effectively O(1) because there are only 26 characters a-z.
Step-by-step trace
1function isAnagram(s: string, t: string): boolean {2 if (s.length !== t.length) return false3 const count = new Map<string, number>()4 // Count character frequencies in s5 for (const ch of s) count.set(ch, (count.get(ch) ?? 0) + 1)6 // Subtract frequencies using t7 for (const ch of t) {8 const freq = count.get(ch)9 if (!freq) return false // char missing from s or already used up10 count.set(ch, freq - 1)11 }12 return true13}Edge cases to remember
Two empty strings — both have length 0, return true (they count as anagrams of each other).
Different lengths — check this first and return false without scanning.
Repeated characters: s="aab", t="baa" — the counts must match the frequencies exactly.
More of a character in t than in s: s="ab", t="aab" — the count of "a" is already 0 but t needs another one → return false.