Valid Anagram
Asked at Google, Amazon, Microsoft, Meta
Difficulty
Easy
Time
O(n)
Space
O(1)
Pattern
Hash Table
Companies
4
Problem
You are given two strings, s and t. Return true if t is an anagram of s, and false otherwise.
Two strings are anagrams when they use exactly the same characters the same number of times, just possibly in a different order. For example, "listen" and "silent" are anagrams because each has one l, one i, one s, one t, one e and one n.
A quick rule that saves work: if the two strings have different lengths, they can never be anagrams, so you can return false right away. Only lowercase English letters appear in the input.
Same letters, different order
Constraints
- ●
1 <= s.length, t.length <= 5 * 10^4 - ●
s and t consist of lowercase English letters only
Examples
s = "anagram", t = "nagaram"trues = "rat", t = "car"falseAsked At
4 companies| Company | Difficulty | |
|---|---|---|
| Easy | View all Google questions → | |
| Amazon | Easy | View all Amazon questions → |
| Microsoft | Easy | View all Microsoft questions → |
| Meta | Easy | View all Meta questions → |
How to Think About It
Brute force: sort both strings and compare. If sorted(s) == sorted(t), they are anagrams. Sorting takes O(n log n) time and O(n) space (strings are immutable in most languages, so sorting creates new copies). This is simple but not optimal.
Optimal: count character frequencies. Create a frequency array or hash map for string s, then decrement counts using string t. If all counts are zero at the end, they are anagrams. This is O(n) time and O(1) space (fixed 26 letters for lowercase English).
Alternative optimal: use a single array of 26 counters. Increment for each character in s, decrement for each in t. After processing both strings, check if all counters are zero. One pass through both strings, constant space.
Edge cases: strings of different lengths are never anagrams — check length first. The problem says only lowercase English letters, so a 26-element array works. If Unicode is allowed, use a hash map instead.
Follow-up: "What if the strings are huge?" The array approach still works since the alphabet is fixed. If the interviewer asks about case-insensitivity, convert both to lowercase first.
Optimal Approach
Check if lengths differ — if so, return false immediately. Create a 26-element counter array (all zeros). For each character in s, increment the counter at that character's index. For each character in t, decrement the counter. After processing both strings, check if all 26 counters are zero. If any is non-zero, return false; otherwise return true.
Walkthrough: s = "anagram", t = "nagaram". Both length 6. After s: {a:3, n:1, g:1, m:1, r:1}. After t: all counters return to 0. Result: true.
Time: O(n) — single pass through both strings. Space: O(1) — 26-element array.
One counter array, add then subtract
What Trips People Up in Real Interviews
Sorting without checking length first. If lengths differ, they are not anagrams — return false immediately before doing any work.
Using a hash map when a fixed-size array is simpler. For lowercase English only, an array of 26 is cleaner and faster. Save the hash map for when the alphabet is unknown.
Forgetting to handle the case where one string has extra characters. The decrement approach catches this — a counter will go negative.
Not verifying the frequency count is actually zero at the end. If you just check during iteration, you might miss an early false positive.
Solution Code
O(n) timedef isAnagram(s, t):
if len(s) != len(t):
return False
counts = [0] * 26
for c in s:
counts[ord(c) - ord('a')] += 1
for c in t:
counts[ord(c) - ord('a')] -= 1
return all(c == 0 for c in counts)Frequently Asked Questions
What is the Valid Anagram problem?
Valid Anagram asks you to determine whether two strings are anagrams of each other — meaning they contain the same characters with the same frequencies, just in a different order. This is a classic frequency-counting problem that tests your ability to choose between sorting and hash-map approaches.
How do you solve Valid Anagram?
The optimal approach runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Valid Anagram?
Valid Anagram is asked at Google, Amazon, Microsoft, Meta. It is a easy difficulty problem.
What are common mistakes on Valid Anagram?
- Sorting without checking length first. If lengths differ, they are not anagrams — return false immediately before doing any work.
- Using a `hash map` when a fixed-size array is simpler. For lowercase English only, an array of 26 is cleaner and faster. Save the `hash map` for when the alphabet is unknown.
- Forgetting to handle the case where one string has extra characters. The decrement approach catches this — a counter will go negative.
- Not verifying the frequency count is actually zero at the end. If you just check during iteration, you might miss an early false positive.