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).
Frequency Map Visualized#
Let's take the example of this visualization: s = "ANAGRAM" and t = "NAGARAM", the same pair from the problem statement above.
Press play and watch the two phases run in order. First every character of s is counted up into the frequency map. Then every character of t is counted back down, and the chips drain toward zero one letter at a time. Keep an eye on the A chip in particular: it climbs to 3 during the count phase and has to land exactly on 0 by the end. A chip going negative, or any chip finishing non-zero, is what makes the answer false.
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.