Valid Anagram
Asked at Google, Amazon, Microsoft, Meta
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.
Asked At
| 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.
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
def 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.