242. Valid Anagram — DSA Atlas

242

EasyArrays and HashingHash map / character countingFrequency signature match

Valid Anagram

Given two strings s and t, return true if t is an anagram of s, meaning t uses exactly the same characters as s with the same multiplicities.

Open official problem prompt ↗

In plain English

Determine whether one string is a rearrangement of another.

Picture it like this

Like checking two bags of Scrabble tiles: dump each out and confirm you have the same letters in the same quantities, regardless of the order you drew them.

Example

Input: s = "anagram", t = "nagaram"
Output: true
Why: Both strings contain three a's, one n, one g, one r, and one m, so their letter counts match.

Constraints

1 <= s.length, t.length <= 5 * 10^4s and t consist of lowercase English letters

Pattern lesson

See the pattern, then code

Frequency signature match

↗

Arrays and Hashing

Duplicates, frequency counts, grouping, membership tests, or pair lookup.. Two strings are anagrams exactly when their per-character counts are identical, so reduce each string to a count map and compare.

New words, made simpleKnow these before the algorithm

Anagram: A string formed by rearranging the characters of another, using each character the same number of times.
Frequency map: A mapping from each character to how many times it occurs.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Sort both strings

Correct but the sort is unnecessary overhead.

Sort s and t and compare the sorted forms.

Time O(n log n)Space O(n)

Best choiceCounter comparison

Linear time; the map has at most 26 keys so space is constant.

Build a character count for each string and compare the two maps.

Time O(n)Space O(1)

The rule we keep true

Invariant

Two strings are anagrams if and only if their frequency maps are equal, a fact that holds independent of character order.

Why this is correct

Reasoning

An anagram permutes characters without adding or removing any, so it preserves every character's count. Equal length plus equal counts for all 26 letters is both necessary and sufficient for the strings to be permutations of each other.

The algorithm in three movesSay these aloud before coding

1If the lengths differ, they cannot be anagrams

count(s): a:3,n:1,g:1,r:1,m:1

2Tally the frequency of each character in s

count(t): a:3,n:1,g:1,r:1,m:1

3Tally the frequency of each character in t

maps equal -> true

4Return whether the two frequency maps are equal

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readlen(s)=7, len(t)=7

2 · AskDo the lengths match?

3 · Update state7 == 7

4 · ResultEqual, so continue.

Key takeaway

Both strings reduce to the same letter-count signature (three a's highlighted).

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 5-6Fast length reject
Different lengths can never be anagrams, so this short-circuits before counting.
2
Lines 7Compare signatures
Counter builds both frequency maps and the equality check compares all character counts at once.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Different lengths return false immediately
Identical strings are trivially anagrams
Single-character strings compare a lone count
Same letters but different counts, e.g. "aacc" vs "ccac", return false

Common beginner mistakes

Comparing sums or sets of characters instead of counts, which misses multiplicity differences
Assuming case-insensitivity; the problem uses lowercase letters only
Forgetting the length guard, which is not strictly required but avoids counting mismatched-size inputs

Check your understanding

How would the approach change for a full Unicode alphabet rather than 26 lowercase letters?

Valid Anagram

Valid Anagram

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Arrays and Hashing