Valid Anagram

Given two strings s and t, return true if t is an anagram of s.

Why this is worth learning

Anagrams are exactly equality of frequency vectors. The lowercase alphabet allows a fixed-size difference vector instead of sorting or a general hash map.

Before coding: one-minute experiment

Are "aabb" and "abbb" anagrams, and which counts disprove it?

Function signature

func IsAnagram(s string, t string) bool

Inputs / outputs

• s, t: input strings.
• Return: true if they are anagrams, else false.

Example

s = "anagram", t = "nagaram"
Output: true

Constraints

• 0 <= len(s), len(t) <= 100_000
• Strings contain only lowercase letters.

Core idea (near-solution)

Two strings are anagrams if every letter appears the same number of times. Use a 26-count array.

Invariant: after processing, all counts must return to zero.

Algorithm (step-by-step)

1. If the byte lengths differ, return false.
2. Initialize all 26 differences to zero.
3. At each index i, increment the entry for s[i] and decrement the entry for t[i].
4. After processing both complete strings, return true exactly when every entry is zero.

A negative intermediate difference is allowed in this simultaneous scan: s="ab", t="ba" first gives +1 for a and -1 for b, then both return to zero. Early rejection on a negative count belongs to the different strategy that fully counts s before consuming t.

Correctness sketch

After processing equal-length prefixes of s and t, each coordinate holds the number of that letter in the source prefix minus its number in the target prefix. Adding the next source letter and subtracting the next target letter preserves this invariant. At termination, all coordinates are zero exactly when every letter has equal multiplicity in the complete strings. Equal multisets can be rearranged into one another, while any nonzero coordinate proves a surplus or deficit that no rearrangement can fix. An initial length mismatch immediately rules out equal multisets.

Trace (hand walkthrough)

Example input:
s = "anagram", t = "nagaram"
Output: true

Walk:
- count s: a:3 n:1 g:1 r:1 m:1
- subtract t="nagaram" -> all counts return to 0 -> true

Pitfalls to avoid

• Forgetting length check.
• Rejecting a negative count before all source bytes have been added in the simultaneous difference scan.

Debugging lens

Test empty strings, equal lengths with unequal counts, and reordered repeated letters. Merely checking that both strings contain the same distinct letters is not sufficient.

Complexity

• Time: O(n)
• Extra space: O(1).

Implementation notes (Go)

• Check length equality first.
• Use a [26]int count array for lowercase letters.

Reconstruction checkpoint

Are "aabb" and "abbb" anagrams, and which counts disprove it?

Return to Hash Map · Module quiz