Count Anagram Pairs

mediumSave

CountingHash TableSortingString

You are given an array of strings, words. Your task is to count the total number of 'anagram pairs' within this array. Two strings are considered an anagram pair if one can be formed by rearranging the letters of the other. For example, "listen" and "silent" are anagrams. A pair (words[i], words[j]) is counted if i < j and words[i] is an anagram of words[j]. Note that (words[i], words[j]) and (words[j], words[i]) represent the same pair and should only be counted once. The comparison should be case-insensitive, but for this problem, all input strings consist of lowercase English letters.

Example 1

Input

[
  "[\"cat\", \"act\", \"tac\", \"dog\", \"god\"]"
]

Output

Explanation. The anagram pairs are: ("cat", "act"), ("cat", "tac"), ("act", "tac"), and ("dog", "god").

Example 2

Input

[
  "[\"listen\", \"silent\", \"hello\", \"world\", \"enlist\"]"
]

Output

Explanation. The anagram pairs are: ("listen", "silent"), ("listen", "enlist"), and ("silent", "enlist").

Example 3

Input

[
  "[\"abc\", \"def\", \"ghi\"]"
]

Output

Explanation. No anagram pairs are present in the array.

Example 4

Input

[
  "[\"a\", \"a\", \"a\", \"b\"]"
]

Output

Explanation. The three 'a's form 3 pairs: (index 0, index 1), (index 0, index 2), and (index 1, index 2).

Example 5

Input

[
  "[\"rat\", \"tar\", \"art\", \"star\", \"rats\"]"
]

Output

Explanation. The anagram pairs are: ("rat", "tar"), ("rat", "art"), and ("tar", "art"). "star" and "rats" are not anagrams of each other or the others.

Follow-up: Consider how your solution would change if the input strings could contain uppercase letters, numbers, or special characters. What if the strings could be very long (e.g., up to 10^5 characters)?

Constraints:

- `1 <= words.length <= 10^4` - `1 <= words[i].length <= 20` - `words[i]` consists only of lowercase English letters (`'a'-'z'`).

Views: 4