242. Valid Anagram - Detailed Explanation
Problem Statement
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, using all the original letters exactly once.
Examples
Example 1:
Input:
s = "anagram", t = "nagaram"
Output:
true
Explanation:
The letters in "anagram"
can be rearranged to form "nagaram"
, so they are anagrams.
Example 2:
Input:
s = "rat", t = "car"
Output:
false
Explanation:
The letters in "rat"
cannot be rearranged to form "car"
, so they are not anagrams.
Example 3:
Input:
s = "aacc", t = "ccac"
Output:
false
Explanation:
Both words have the same set of characters, but their counts do not match (two "a"
s in s
vs. one "a"
in t
).
Constraints:
1 <= s.length, t.length <= 5 * 10^4
s
andt
consist of lowercase English letters.
Follow-up:
What if the inputs contain Unicode characters? How would you adapt your solution?
Hints to Guide the Thought Process
-
Sorting Approach:
- If two words are anagrams, they contain the same letters in the same frequency.
- Sorting the strings will put identical letters in the same order.
- If the sorted versions of both strings are equal, they are anagrams.
-
Frequency Count Approach (HashMap or Array):
- Instead of sorting, we can count the occurrences of each letter in both strings.
- If the letter frequencies match, the strings are anagrams.
-
Optimized One-Pass Counting:
- Since the strings consist only of lowercase English letters (
a-z
), we can use a fixed-size array of length 26 instead of a hash map for counting.
- Since the strings consist only of lowercase English letters (
-
Handling Unicode Characters (Follow-up Question):
- If the input contains Unicode characters (not just
a-z
), we should use a hash map (dictionary in Python, HashMap in Java) instead of an array.
- If the input contains Unicode characters (not just
Approach 1: Sorting the Strings
Idea:
- Sort both
s
andt
and compare them. - If they are anagrams, sorting them will result in the same string.
Steps:
- Convert both
s
andt
into lists of characters. - Sort both lists.
- Compare if they are identical.
Time and Space Complexity:
- Sorting takes O(n log n) time.
- Storing sorted strings requires O(n) space.
Python Code:
Java Code:
Why this works:
Sorting arranges the letters in order. If two strings contain the same characters in the same frequency, their sorted versions will be identical.
Drawbacks:
- Sorting takes O(n log n) time, which is slower than O(n) frequency-based approaches.
- Extra space is needed to store sorted versions.
Approach 2: Using Hash Map (Frequency Counting)
Idea:
- Count the occurrences of each letter in
s
andt
using a hash map (dictionary). - If both maps are identical,
t
is an anagram ofs
.
Steps:
- Check if the lengths of
s
andt
are different. If so, returnfalse
. - Create a frequency dictionary for
s
and another fort
. - Compare the frequency dictionaries.
Time and Space Complexity:
- O(n) time: We traverse
s
andt
once. - O(n) space: We store the character counts.
Python Code:
Java Code:
Why this works:
- We count characters efficiently in O(n) time.
- Using a hash map makes it flexible for Unicode characters.
Drawbacks:
- Uses extra space for the hash map (O(n) space).
Approach 3: Using an Array (Optimized Counting)
Idea:
- Since
s
andt
contain only lowercase English letters (a-z
), we can use an array of size 26 instead of a hash map.
Steps:
- Check if
s
andt
have different lengths. If so, returnfalse
. - Create an array
count[26]
initialized to zero. - Increment values for characters in
s
, decrement fort
. - If the final count array contains only zeros,
t
is an anagram ofs
.
Time and Space Complexity:
- O(n) time: We traverse
s
andt
once. - O(1) space: The array size is fixed (26).
Python Code:
Java Code:
Why this works:
- Uses a fixed size O(1) array instead of a hash map.
- Efficient O(n) time complexity.
Drawbacks:
- Limited to lowercase English letters (
a-z
).
Summary of Approaches
Approach | Time Complexity | Space Complexity | Notes |
---|---|---|---|
Sorting (sorted() or Arrays.sort() ) | O(n log n) | O(n) | Simple, but not the fastest |
Hash Map (Counter() or HashMap ) | O(n) | O(n) | Works for Unicode characters |
Fixed-Size Array (count[26] ) | O(n) | O(1) | Fastest for a-z letters |
Edge Cases to Consider
- Different lengths (
len(s) != len(t)
) → Returnfalse
immediately. - Same characters but different counts (
s = "aacc", t = "ccac"
) → Not an anagram. - Empty strings (
s = "", t = ""
) → Should returntrue
. - Large inputs (
s
andt
close to5 * 10^4
length) → Use the O(n) methods (hash map
orarray
) instead of sorting.
Follow-up: Unicode Support
- The array solution (
count[26]
) does NOT work for Unicode characters. - Use a
HashMap<Character, Integer>
(Java) orCounter()
(Python) to support Unicode.
Best Approach
- For English lowercase letters (
a-z
): Use the array approach (O(n), O(1) space). - For general Unicode text: Use the hash map approach (O(n), O(n) space).
Relevant Problems
- Group Anagrams
- Find All Anagrams in a String
- Longest Palindrome by Rearranging Letters
- Check if Two Strings Are Close
- Ransom Note
- Minimum Steps to Make Two Strings Anagram
- Isomorphic Strings
GET YOUR FREE
Coding Questions Catalog
