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 and t 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.
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.

Approach 1: Sorting the Strings

Idea:

Sort both s and t and compare them.
If they are anagrams, sorting them will result in the same string.

Steps:

Convert both s and t 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:

Python3

. . . .

Java Code:

Java

. . . .

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 and t using a hash map (dictionary).
If both maps are identical, t is an anagram of s.

Steps:

Check if the lengths of s and t are different. If so, return false.
Create a frequency dictionary for s and another for t.
Compare the frequency dictionaries.

Time and Space Complexity:

O(n) time: We traverse s and t once.
O(n) space: We store the character counts.

Python Code:

Python3

. . . .

Java Code:

Java

. . . .

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 and t contain only lowercase English letters (a-z), we can use an array of size 26 instead of a hash map.

Steps:

Check if s and t have different lengths. If so, return false.
Create an array count[26] initialized to zero.
Increment values for characters in s, decrement for t.
If the final count array contains only zeros, t is an anagram of s.

Time and Space Complexity:

O(n) time: We traverse s and t once.
O(1) space: The array size is fixed (26).

Python Code:

Python3

. . . .

Java Code:

Java

. . . .

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)) → Return false immediately.
Same characters but different counts (s = "aacc", t = "ccac") → Not an anagram.
Empty strings (s = "", t = "") → Should return true.
Large inputs (s and t close to 5 * 10^4 length) → Use the O(n) methods (hash map or array) instead of sorting.

Follow-up: Unicode Support

The array solution (count[26]) does NOT work for Unicode characters.
Use a HashMap<Character, Integer> (Java) or Counter() (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).