Valid Anagram
Problem Statement
Given two strings s and t, return true if t is an anagram of s, and false otherwise. An anagram uses exactly the same characters with exactly the same multiplicities, possibly in a different order.
Input
Two lowercase strings s and t.
Output
A boolean: true when the two strings have identical character counts, otherwise false.
Constraints
- •
1 <= s.length, t.length <= 5 * 10^4 - •
s and t consist of lowercase English letters
Examples
Example 1
s = anagram, t = nagaram
trueExample 2
s = rat, t = car
falseExample 3
s = a, t = ab
falseLearning Objectives
- Recognise anagram validation as equality of character frequencies.
- Use a fixed 26-entry array instead of a general map for lowercase English letters.
- Balance increments from one string with decrements from the other string.
- Short-circuit immediately when lengths differ.
Intuition
Pattern Recognition
The signal is that order does not matter, but multiplicity does. Sorting both strings would work, but it costs O(n log n). For lowercase English letters, a fixed-size count array compares the two multisets in linear time.
Think of one array as a balance sheet. Each character in s adds one credit, and each character in t removes one credit. If the strings are anagrams, every letter balance returns to zero.
Common mistakes
- ×Checking only whether both strings contain the same distinct characters and ignoring multiplicity.
- ×Forgetting the early length check, which can make partial balances look misleading.
- ×Using a 128-entry table without explaining the lowercase constraint or alphabet assumption.
- ×Returning true before verifying that every count is back to zero.
Algorithm Explanation
Key idea
Use an array of 26 balances. For each index, increment the count for s[index] and decrement the count for t[index]. Equal final balances mean every letter appeared the same number of times in both strings.
Walkthrough
For s = anagram and t = nagaram, both strings have length 7. As the scan progresses, letters from s add to the balance and letters from t subtract from it. The temporary balances may be non-zero during the scan, but after all characters are processed, every letter count is zero, so the strings are anagrams.
Algorithm
- If the lengths differ, return false.
- Create an integer array balance of length 26.
- For each index, increment balance[s[index] - 'a'].
- In the same loop, decrement balance[t[index] - 'a'].
- Scan balance and return false if any count is non-zero.
- Return true when all balances are zero.
Solutions
Solution: Balanced character counts
The fixed alphabet lets us replace a hash map with an integer array. Incrementing for s and decrementing for t makes the final all-zero check a direct test for equal frequencies.
Step-by-step
- Return false immediately if the strings have different lengths.
- Allocate a 26-entry balance array.
- For each index, add one for the character from s and subtract one for the character from t.
- After the scan, inspect all 26 balances.
- Return true only if every balance is zero.
O(n)
O(1)
The scan is linear and the 26-entry array is constant space.
Java implementation
Dry Run
Sample input
s = anagram, t = nagaram. Track the balance changes for the letters touched at each index.
| step | s char | t char | balance change | non-zero balances after step |
|---|---|---|---|---|
| 1 | a | n | +a, -n | a:+1, n:-1 |
| 2 | n | a | +n, -a | all zero |
| 3 | a | g | +a, -g | a:+1, g:-1 |
| 4 | g | a | +g, -a | all zero |
| 5 | r | r | +r, -r | all zero |
| 6 | a | a | +a, -a | all zero |
| 7 | m | m | +m, -m | all zero |
Every temporary imbalance is cancelled by the end, so the final all-zero balance array proves the strings are anagrams.
Interview Tips
Mention the alphabet assumption before choosing int[26]. The solution is linear because you never sort; you only count. If the interviewer expands the character set, switch from the fixed array to a hash map or a larger indexed table.
Likely follow-ups
- How would the solution change for Unicode strings?
- How would you find all anagram positions of **p** inside a larger string **s**?
- How would you validate anagrams while ignoring spaces, punctuation, and case?
- How would you compare many strings against the same base word efficiently?
Similar Problems
Key Takeaways
- Anagrams are equal frequency vectors, not equal sorted positions.
- A 26-entry array is the simplest count structure for lowercase English letters.
- Increment and decrement in one pass to compare two strings cleanly.
- Always reject unequal lengths before counting.