The Problem
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.
Approach 1: Sorting — O(N log N)
If two strings are anagrams of each other, sorting both strings will produce identical results.
- Time Complexity: $O(N \log N)$ where $N$ is the length of the strings (due to sorting).
- Space Complexity: $O(N)$ or $O(1)$ depending on the language's sorting algorithm implementation (some copy the string).
Approach 2: Hash Map (Frequency Map) — O(N)
Since an anagram requires the exact same characters with the same frequencies, we can count the occurrences of each character in both strings.
We create a frequency map for s, then iterate through t to decrement counts. If we find a character not in the map, or if any count drops below zero, they aren't anagrams.
- Time Complexity: $O(N)$ because we iterate through the strings of length $N$ exactly once.
- Space Complexity: $O(1)$ since the alphabet size is constant (e.g., 26 lowercase English letters).
Hash Map Visualized
Here's how a Hash Map stores keys and manages lookups in $O(1)$ average time. Try mapping string keys to bucket coordinates:
Key Insight
Frequency maps let us verify character matches in $O(N)$ time by counting occurrences. While sorting is simpler to write, frequency counting is more optimal at scale, especially for large inputs or streams where sorting is impractical.