Valid Anagram
Understanding the Problem
Two strings are anagrams if and only if they contain the exact same characters with the exact same frequencies. "listen" and "silent" are anagrams because both have one 'l', one 'i', one 's', one 't', one 'e', and one 'n'. "hello" and "world" are not, because their character counts differ.
The problem reduces to checking whether two strings have identical character frequency distributions. We can do this by sorting both strings, or by counting characters directly.
Key Constraints:
1 <= s.length, t.length <= 5 * 10^4→ With n up to 50,000, an O(n^2) comparison would mean 2.5 billion operations, which is too slow. O(n log n) and O(n) both work.s and t consist of lowercase English letters→ Only 26 possible characters, so a fixed-size array of length 26 is enough to count frequencies. A hash map is needed only if the alphabet is unbounded (the Unicode follow-up).
Approach 1: Sorting
Intuition
Sort both strings and compare them. If the sorted versions are identical, the original strings contain the same characters in the same quantities, only in a different order. If they differ at any position, the strings hold different multisets of characters and cannot be anagrams.
Sorting normalizes order: it forces any anagram into the same canonical sequence. Two bags of Scrabble tiles arranged alphabetically produce identical rows if and only if the bags hold the same tiles.
Algorithm
- If
sandthave different lengths, returnfalseimmediately. - Sort both strings alphabetically.
- Compare the sorted strings character by character.
- If they match, return
true. Otherwise, returnfalse.
Example Walkthrough
Input:
After sorting both strings:
Both sorted strings are identical, so we return true.
Code
- Time Complexity: O(n log n). Sorting each string takes O(n log n). The comparison is O(n), so the sort dominates.
- Space Complexity: O(n). Most sorting algorithms need O(n) space for the sorted copy. In languages like Python and JavaScript, creating sorted copies explicitly uses O(n) space.
Sorting establishes a full ordering of every character, but the answer only depends on whether the frequencies match. Counting characters directly avoids the sort and brings the time down to linear.
Approach 2: Hash Map (Frequency Count)
Intuition
Count how often each character appears in both strings and compare the counts. Two strings are anagrams if and only if every character appears the same number of times in each.
The problem guarantees only lowercase English letters, so a fixed-size array of length 26 replaces the hash map. Indexing the array by char - 'a' gives constant-time access, and the space stays constant regardless of input length.
A single array handles both strings at once: increment the count for each character in s, decrement it for each character in t. After processing both strings, every count is the frequency in s minus the frequency in t. The strings are anagrams exactly when every entry returns to zero.
Incrementing and decrementing inside the same loop relies on s and t having equal length, which the early length check guarantees. Index i is always valid for both strings, so a single pass over indices 0..n touches every character of s and every character of t. Without the length guard, this loop would read out of bounds.
Algorithm
- If
sandthave different lengths, returnfalse. - Create a frequency array of size 26 (one slot per letter).
- For each character in
s, increment the corresponding count. - For each character in
t, decrement the corresponding count. - If any count is not zero, return
false. Otherwise, returntrue.
Example Walkthrough
Code
- Time Complexity: O(n). One pass through both strings simultaneously, plus a final check over 26 slots (constant).
- Space Complexity: O(1). The frequency array has a fixed size of 26, regardless of input length.
This approach is optimal in Big-O terms, but it depends on the alphabet being fixed at 26 lowercase letters. The follow-up asks what changes for Unicode input, where the character set is far larger and an array indexed by char - 'a' no longer applies.
Approach 3: Hash Map (Arbitrary Alphabet)
Intuition
The counting idea does not require a 26-slot array. Replacing the array with a hash map keyed by the character itself removes the assumption that input is lowercase ASCII, so the same frequency-difference logic works for Unicode, mixed case, digits, or any alphabet.
The map stores only the characters that appear, so its size is bounded by the number of distinct characters rather than a fixed 26. Everything else mirrors Approach 2: increment for s, decrement for t, and check that every stored count is zero.
Algorithm
- If
sandthave different lengths, returnfalse. - Create an empty hash map from character to count.
- For each character in
s, increment its count in the map. - For each character in
t, decrement its count in the map. - If every value in the map is zero, return
true. Otherwise, returnfalse.
Example Walkthrough
Take s = "rat" and t = "car", which have equal length but are not anagrams. The first pass builds the counts for s, and the second pass subtracts the counts for t.
After both passes, map['t'] is 1 and map['c'] is -1, so not every count is zero and the function returns false. For an anagram like "anagram" and "nagaram", every entry would cancel back to zero and the function would return true.
Code
- Time Complexity: O(n). One pass over each string, plus a final pass over the map entries. Hash map operations are O(1) on average.
- Space Complexity: O(k), where k is the number of distinct characters. For lowercase letters k is at most 26, so this is effectively constant, but for an arbitrary alphabet the map grows with the distinct characters present.