A sign maker glues two word banners together and then rearranges all of their letter tiles.
The pair is mirror-ready if the combined tiles can be arranged into a palindrome (a string that
reads the same forwards and backwards). Given the list words, return the number of index pairs
(i, j) with i < j such that words[i] and words[j] together are mirror-ready. Equal words
at different indexes are different banners.
Examples
Input: words = ["ab", "ba", "c", "abc", "aa"]
Output: 4
Explanation: ab+ba, ab+abc, ba+abc and c+aa are mirror-ready.
For example "ab"+"abc" has tiles a, a, b, b, c, which form "abcba".
"ab"+"c" is not: a, b and c would each appear once.
Input: words = ["xy", "z"]
Output: 0
Constraints
0 <= len(words) <= 2 * 10**41 <= len(words[i]) <= 20, lowercase letters only.- Target complexity: O(n * 26) dictionary lookups.
Goals
- Reduce a word to the set of letters it holds an odd number of times
- Say when two words together can be rearranged into a palindrome
- Count partners by looking up a signature and its one-letter neighbours