Count Anagram Groups
Medium · rating 1400 · Strings, Hashing, Sorting
The first line contains n. Each of the next n lines is a lowercase word. Print the number of groups when words that are anagrams of one another are grouped together.
Constraints: 1 ≤ n ≤ 104
Editorial
Approach
Two words are anagrams exactly when their sorted letters match, so a word's sorted string is a canonical key for its group. Insert every word's key into a set; the number of distinct keys is the number of groups.
keys = {''.join(sorted(w)) for w in words}
print(len(keys))Alternative key
A 26-letter frequency tuple works as the key too, trading the O(L log L) sort for an O(L) count per word.
Complexity
Time: O(n × L log L). Space: O(n).
Related problems
- Election Winner — Medium
- Longest Substring Without Repeats — Medium
- Anagram Check — Medium
- Most Common Word — Medium
- Distinct Words — Easy
- Unique Visitors — Easy