Valid Anagram: Checking for Character Rearrangements
The Prompt
Given two strings `s` and `t`, return `true` if `t` is an anagram of `s`, and `false` otherwise. An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Understanding the Problem
Two strings are anagrams when they use exactly the same letters exactly the same number of times — order is irrelevant. The classic shortcut is to sort both strings and compare: correct, but O(n log n), and the sort is doing far more work (full ordering) than the question needs (just matching counts).
What actually matters is each string's letter histogram. If the histograms match, the strings are anagrams. Building a histogram is a single O(n) pass, and comparing two histograms over a fixed alphabet is O(1)-ish — 26 slots for lowercase English.
The Interview Flow
Interviewer
How would you check if two strings are anagrams?
Candidate
First, I should check if they have the same length. If not, they can't be anagrams. If they do, one approach is to sort both strings and compare them. If the sorted strings are equal, they are anagrams. This would be O(n log n) where n is the length of the strings.
Interviewer
Good. Can you think of an O(n) solution?
Candidate
Yes, using a hash map or a frequency array. I can iterate through the first string and count the frequency of each character. Then, I iterate through the second string and decrement the count for each character. If I ever encounter a character that is not in the map or its count is already zero, they are not anagrams. Finally, all counts in the map must be zero.
Interviewer
That's a great approach. Please implement it.
Why does one frequency map suffice?
You do not even need two histograms. Increment counts while scanning s, then decrement while scanning t. If t is an anagram, every decrement lands on a positive count and everything ends at zero. If any count would go negative, t used a letter more times than s has it — fail immediately. The length check up front (unequal lengths can never be anagrams) makes "no count ends positive" automatic.
Time is O(n) — two linear passes — and space is O(1), since the map never holds more than 26 keys regardless of how long the strings are. That fixed-alphabet observation is what turns "hash map" into "constant space" and is worth saying out loud.
O(n) Solution using a Frequency Map
- First, check if the lengths of the two strings `s` and `t` are equal. If not, they cannot be anagrams, so return `false`.
- Create a hash map (or an array of size 26 for lowercase English letters) to store character frequencies.
- Iterate through the first string `s`, and for each character, increment its count in the frequency map.
- Iterate through the second string `t`. For each character, decrement its count. If a character is not in the map or its count becomes negative, return `false`.
- If the loop for `t` completes without issues, it means the strings are anagrams. Return `true`.
Try it yourself
Write your solution and run it against 3 test cases.
JavaScript, TypeScript & Python run sandboxed in your browser; other languages run on the execution server. Your code is saved locally as you type.
Final Solution
function isAnagram(s, t) {
if (s.length !== t.length) {
return false;
}
const charCount = {};
for (const char of s) {
charCount[char] = (charCount[char] || 0) + 1;
}
for (const char of t) {
if (!charCount[char]) {
return false;
}
charCount[char]--;
}
return true;
}Explanation
Check s = "anagram" against t = "nagaram" with one counter map.
1Pass 1 over s: increment each letter. Final counts: a: 3, n: 1, g: 1, r: 1, m: 1 (total 3+1+1+1+1 = 7 = len(s)).
2Pass 2 over t: decrement. 'n': 1 → 0, then 'a': 3 → 2. Every decrement lands on a positive count, so no violation yet.
3Finish t: g → 0, a: 2 → 1 → 0 across the remaining a's, r → 0, m → 0. All counts hit zero — return true.
Complexity Analysis
TIME
O(n)
SPACE
O(1)
Finished working through this one?
Mark it complete to track it on your Data Structures path.