LCC/Moose '19 Contest 1 S4 - Morphgrams

View as PDF

Submit solution


Points: 10 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem types

Justine loves learning about the different ways in which words can be related. Recently, she learned about anagrams: a pair of words where the order of the letters of one word can be rearranged to form another. For example, "listen" is an anagram for "silent".

Learning about anagrams made Justine wonder: what if instead of changing the positions of the letters, the positions stay the same but the letters themselves change? Justine has decided to call such pairs of words morphgrams, and is now interested in finding some cool examples of morphgrams. Can you help her find some?

Formally, one word is a morphgram of another if there exists a 1-1 character mapping (each character is mapped to at most once) that, when applied to the first word, produces the second. See the sample input for examples.

Input Specification

The first line of input contains an integer N (1 \le N \le 100,000), the number of words that Justine knows. The next N lines each contain a single, upper-case word. The total size of all the words is at most 10^6 characters.

For 40 out of 100 points, N \le 1,000 and the total size of all the words is at most 10,000 characters.

Output Specification

Output the number of pairs of words that are morphgrams.

Sample Input 1

6
CRITIC
FOOD
MOON
AURORA
MODE
ALLY

Sample Output 1

4

Explanation of Sample Input

"FOOD" is a morphgram of "ALLY" under the mapping F \to A, O \to L, D \to Y. The remaining pairs are "FOOD / MOON", "MOON / ALLY", "AURORA / CRITIC". Note that "MODE" is not a morphgram for "MOON" since both 'O' and 'D' would have to map to 'O', breaking the 1-1 requirement.


Comments

There are no comments at the moment.