Tolstoy's anagrams
A crossword compiler is looking for anagrams in War and Peace: different words made of the same letters, like «краем», «рамке» and «мраке» (“at the edge”, “in a frame”, “in darkness”). They have written out the words of the novel in a row, as they go in the text, with repeats. Help them: find all the groups of anagrams and the largest of them.
What matters is which letters a word has and how many times each, not their order: «кот», «ток» and «кто» form one group, but «тот» and «то» do not, because they have different numbers of the letter «т». One and the same word met in the text several times is one word. A group is at least two different words.
One of the tests is the whole vocabulary of the novel in the Russian original, 47,585 different words; another is its English translation.
Input
The first line holds the number n (1 ≤ n ≤ 200,000). Then come n words separated by spaces and line breaks. A word consists of lowercase Cyrillic letters (а–я, ё) or lowercase Latin letters, and its length is from 1 to 30.
Output
The first line holds the number of anagram groups. If it is greater than zero, the second line holds the largest group: its words in increasing order, separated by spaces. Words are compared by character codes, so Latin comes before Cyrillic, and «ё» after «я». If there are several largest groups, print the one whose first word is smaller.
Examples
Example 1
8 кот ток кто сон нос лев вел кот
3 кот кто ток
Example 2
6 мир рим мир то тот мир
1 мир рим
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 10 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Comparing each word with each is 47,585² / 2, more than a billion pairs. You need a way to say at once which group a word falls into without looking at the others.
2Hint 2
Devise a “passport” for a word: a string that is the same for all anagrams and different for all other words. Then the groups are simply words with the same passport, and a dictionary “passport → set of words” will gather them.
3Hint 3
Will the sum of letter codes do? Anagrams have equal sums. Compute the sums for «ад» and «бг».
4The idea
A word’s passport is its letters sorted alphabetically: for «краем», «рамке» and «мраке» it is «акемр». Two words are anagrams exactly when their sorted letters coincide, so such a key is never wrong either way. Put each word into a hash table by this key, into a set, so that repeats from the text do not count as different words. The groups are the sets with at least two words.
5Walkthrough
One pass over the words: the key "".join(sorted(w)), and the set groups[key] gets the word. Then pick the sets of size two and up, sort the words inside and take the largest; with equal sizes, the one whose first word is smaller. In Go strings are compared byte by byte, and in UTF-8 byte order agrees with the order of character codes, so «ё» comes after «я» there too.
Why not the sum of codes: it is a hash, not a passport. Equal sums occur for words that are not anagrams at all: «ад», «бг» and «вв» all sum to 2148. In the novel’s vocabulary there are hundreds of such mergers, and instead of 1126 groups you get 1558. A hash is good for quickly sorting words into buckets, but whether keys are equal must be decided by exact comparison; that is how any hash table works.
It can also be done without sorting: the passport is a vector of 33 letter counts. For long words this is faster; for the words of the novel it makes no difference.
5+Solution
6Complexity
Sorting the letters of a word of length L is O(L log L), dictionary operations are O(L) on average for hashing the key. O(N log L) in all, where N is the total length of all the words, plus sorting the words inside the groups.
7Common mistakes
- A sum of codes or a product of primes instead of sorted letters. The sum merges unrelated words (the third test). A product of primes, one per letter, is an honest passport, but in 32 or 64 bits it overflows, and false matches appear again.
- A set of letters instead of a sorted list.
set("тот")equalsset("то"), although they are not anagrams: how many times a letter occurs is lost. - A list instead of a set. «мир» three times in the text is not a group of three words (the second example).