A test kitchen assigns every recipe a short code made only of lowercase English letters, where each distinct letter stands for one ingredient tag used in that recipe; how many times a letter repeats and the order the letters appear in carry no meaning -- only which distinct letters appear matters. Two recipe codes are called flavor-matched when the set of distinct letters appearing in one code is exactly equal to the set of distinct letters appearing in the other. Given n recipe codes, count how many unordered pairs of recipes (by index) are flavor-matched.
The first line contains one integer n, the number of recipe codes. Each of the next n lines contains one recipe code, a non-empty string of lowercase English letters.
A single integer: the number of index pairs (i, j) with i < j such that recipe i and recipe j are flavor-matched.
Example 1
Input
5 dog god cat tac fox
Expected
2
Explanation
Distinct-letter sets: dog->{d,o,g}, god->{g,o,d} (same as dog, a match), cat->{c,a,t}, tac->{t,a,c} (same as cat, a match), fox->{f,o,x} (matches nothing else). The two matching pairs are (dog,god) and (cat,tac), so the output is 2.
Example 2
Input
3 aab ab ba
Expected
3
Explanation
All three codes reduce to the same distinct-letter set {a,b} (aab has a repeated 'a' but that doesn't change the set). With all 3 codes sharing one signature, every pair among them matches: (aab,ab), (aab,ba), (ab,ba), giving C(3,2) = 3.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →