visual walkthrough
Valid Anagram
Counting characters with a fixed-size array is the base of every anagram and permutation problem.
The idea
Two words are anagrams when they use exactly the same letters the same number of times. Sorting makes that obvious; counting gets there without sorting at all.
With counting, add one for each letter of the first word and take one away for each letter of the second. If everything cancels, they match.
Complexity
| approach | time | space |
|---|---|---|
| Sort both | O(n log n) | O(n) |
| Count letters | O(n) | O(1) |