294. How Many Anagram Groups
Print how many groups the words fall into when words that are anagrams of each other are placed in the same group.
eat tea tan ate nat bat -> 3
Those groups are eat tea ate, tan nat, and bat.
The technique is to give every word a KEY that is identical for anagrams and different otherwise, then count the distinct keys. Sorting a word's letters produces exactly such a key, since anagrams sort to the same string.
That idea, computing a canonical form and hashing on it, is worth more than the problem: it turns "are these equivalent" into "are these equal".
Constraints - `1 ≤ n ≤ 100000` - `1 ≤ word length ≤ 20` - Words are lowercase letters only.
Input
The first line contains an integer n.
Each of the next n lines contains one word of lowercase letters.
Output
Print one integer, the number of anagram groups.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.