HashMap + Combinatorics "Trick" with Clear Explanation & Example - Python
Intuition / Approach\n### Step 1: Count how many words are similar\nReduce each word in words to a non-repeating set of its letters -- let\'s make a key out of 
# Intuition / Approach\n### Step 1: Count how many words are similar\nReduce each word in `words` to a non-repeating set of its letters -- let\'s make a key out of this reduced word in a hash map and initialize it with a count of 1 to denote that we have seen it once so far.\n\nAs we traverse `words`, we will check our map to see whether the current word reduces to something already seen. If it has been seen before, we increase by count by 1.\n\nConsidering Example 2 from the problem description, `words = ["aabb","ab","ba"]`, our final mapping/dictionary at the end of our traversal would look like\n\n```\n# Python dictionary format\nd = { \'ab\': 3}\n```\n\nsince each word in `words` reduces to the same set of letters.\n\n> *Note that the lookup key must be sorted, or you will not be able to identify whether "ba" is similar to "ab"*\n\n### Step 2: Calculate how many pairs can be drawn for each key\nWe now know how many times each word in `words` maps to a reduced `key` after it is itself reduced. \n\nIn combinatorics, there is a formula known as *$n$ choose $k$* which specifies that the number of ways in which groups of size $k$ can be selected from $n$ total objects, where the order of things in each group of size $k$ does not matter, is given by\n\n$$\n{n \\choose k} = \\frac{n\\ !}{k\\ ! (n - k)\\ !}\n$$\n\nIn our problem, we are wanting to count the number of ways we can select a pair of words, so we have $k=2$.\n\nApplying this to Example 2, we have found 3 similar words (based on the `\'ab\'` key) and we would like to know how many ways we can draw pairs from the set of 3 words. \n\nWe find the answer as ${3 \\choose 2} = 3\\ ! / (2\\ ! (3 - 2)\\ ! )= 3$.\n\nIf we had multiple `keys` in our dictionary, we would calculate this for each `key` and sum up the answer.\n\n\n# Complexity: *O(mlogn)*\n\nExplanation - *assuming sizes are not integer-bounded as they actually are in the problem constraints*:\n* for loop: *O(n)*, where *n* is the size of `words`. \n* Calling `sorted()` on each `word`: *O(mlogn)*, where *m* is the largest number of letters for all the words which need to be sorted to create the key for our dictionary. \n  * In this problem, this is actually bounded by a specified constant of 100, so *O(mlogn) = O(100 logn) ~ O(logn)*\n* Dictionary lookups: *O(1)* time\n\nSo we have *O(n) + O(mlogn) + O(1) ~ O(mlogn)* for our final complexity.\n\n# Code\n```\ndef fac(num: int) -> int:\n    # returns n! (factorial function)\n    # for n > 0\n    # You can also use the built-in math.factorial(num) function\n    if num == 1:\n        return num\n    else:\n        return num * fac(num-1)\n\n\nclass Solution:\n\n    def similarPairs(self, words: List[str]) -> int:\n        d = dict()\n\n        for word in words:\n            # Reduce each word to a nonrepeating set of its letters\n            # Transform to string with \'\'.join(list) to use as a dictionary key\n            # The key must be sorted for the lookup\n            w = \'\'.join(sorted(set(word)))\n            if w not in d:\n                # Each reduced word is tracked as "seen" by 1\n                d[w] = 1\n            else:\n                # If the same reduced set has been seen before, add to its count\n                d[w] += 1\n\n        answer = 0\n        for key in d:\n            if d[key] == 2:\n                # If the reduced set of letters has been seen exactly 2x\n                # then that counts as a single pair\n                # We explicitly define this case to avoid division by 0\n                # in the n choose k formula\n                answer += 1\n            elif d[key] > 2:\n                # Directly apply the "n choose k" formula whenever we\n                # encounter a key which has enough words from which pairs\n                # can be drawn\n                num_choose_2 = fac(d[key]) / (2 * fac(d[key] - 2))\n                answer += num_choose_2\n            # (the case when d[key] == 1 is ignored since there aren\'t\n            # enough words to draw pairs from)\n        \n        return int(answer)\n        \n```
['Combinatorics', 'Python', 'Python3']