March 24
Valid Anagram
How to notice that an anagram is about frequency, not order, and justify the move from sorting to counting.
Strings and Frequency Count Beginner 12 min TypeScript
Given two strings s and t, return true if t is an anagram of s, and false otherwise.
An anagram uses the same letters with the same counts, but in a different order.
Example:
Input: s = "anagram", t = "nagaram"
Output: true
What to notice before coding
- Order does not matter. The count of each character does.
- If the lengths are different, the answer is already `false`.
- The problem does not ask you to build the anagram. Only to validate it.
Common mistakes
- comparing only the set of characters and forgetting the counts
- using sorting without being able to explain why it works
Step 1 — Understand what makes an anagram
A lot of people see this problem and think about order.
But order is not the point.
If listen and silent are anagrams, it is not because the letters sit in similar positions. It is because each letter appears the same number of times on both sides.
Step 2 — Write the first correct version
A simple way to solve it is to sort both strings and compare:
export function isAnagram(s: string, t: string): boolean {
if (s.length !== t.length) {
return false
}
const sortedS = s.split('').sort().join('')
const sortedT = t.split('').sort().join('')
return sortedS === sortedT
}
It works because sorting lines up identical characters in the same order.
Step 3 — Understand what sorting is revealing
sort is not magic.
It only makes one thing easier to see:
the frequency of each character must match.
If that is the real rule, you can work with frequency directly.
Step 4 — Count instead of sort
Use a Hash Map to count characters from s.
Then walk through t:
- if a character is missing from the
Map, fail - if a count goes negative, fail
- if everything balances out, it is an anagram
The interactive editor needs JavaScript. You can still read the prompt and copy the starter code below.
Starter code
export function isAnagram(s: string, t: string): boolean {
// your solution here
return false
}
Haven't solved it yet?
Viewing the solution now may reduce learning. It's worth trying a bit more.
Open the reference solution
Without JavaScript, the reference solution is shown inline instead of in a dialog.
Solution
Final complexity
Time: O(n)
Space: O(n)
Solution 1 — Sort and compare O(n log n)
This is the most common baseline.
export function isAnagram(s: string, t: string): boolean {
if (s.length !== t.length) {
return false
}
const sortedS = s.split('').sort().join('')
const sortedT = t.split('').sort().join('')
return sortedS === sortedT
}Good place to start. But the expensive part is the sorting.
Solution 2 — Frequency counting with a Hash Map in O(n)
If anagrams depend on counts, count directly.
export function isAnagram(s: string, t: string): boolean {
if (s.length !== t.length) {
return false
}
const counts = new Map<string, number>()
for (const char of s) {
counts.set(char, (counts.get(char) ?? 0) + 1)
}
for (const char of t) {
const nextCount = (counts.get(char) ?? 0) - 1
if (nextCount < 0) {
return false
}
counts.set(char, nextCount)
}
return true
}You do not need to reorder anything. You only need to guarantee that each letter came in and went out the same number of times.
What to say in the interview
A strong short explanation would be:
The simplest version sorts both strings and compares them, which costs
O(n log n). Since an anagram depends on frequency rather than order, I can count characters with aHash Mapand verify everything inO(n).
That shows that you:
- can explain why the baseline works
- identified the real rule of the problem
- switched tools without losing the thread
When this pattern shows up again
The same pattern comes back when the problem asks you to:
- count occurrences
- compare character distributions
- validate whether two inputs have the same composition
- maintain frequency inside a window
The point is not memorizing “anagram = hash map”.
The point is noticing when the real problem is counting, even if the prompt talks about strings.