8. Complementary Pairs A pair of strings form a complementary pair if there is some permutation of their concatenation that is a palindrome. For example, the strings "abac" and "cab" form a complementary pair since their concatenation is "abaccab" which can be rearranged to form a palindrome, i.e., "bcaaacb". Given an array of
n
strings, find the number of complementary pairs that can be formed. Note: Pairs of strings formed by indices
(i,j)
and
(j,i)
are considered the same. Example Consider stringData
=["abc
," "abcd", "bc", "adc"]. The following complementary pairs can be formed: - ("abc", "abcd"), concatenated string = "abcabcd" arranged as a palindrome - "abcdcba". - ("abc". "bc"), concatenated string = "abcbc" -> "bcacb". ("abcd", "adc"), concatenated string = "abcdadc" -> "acdbdca". Return 3 , the number of complementary pairs. Function Description Complete the function countComplementaryPairs in the editor below. countComplementaryPairs has the following. parameter: string stringData[n]: the strings to pair Returns fong. int the number of complementary pairs that can be formed Constraints -
1≤n≤10 5
-
1≤
length(stringData[i])
≤3∗10 5
-
1≤5um
of the length of strings in stringData
≤3∗
10 5
- All strings consist of lowercase English characters only. Sample Output o 3 Explanation The following complementary pairs can be formed: "eiliblitar" - Tball", bally concatenated string = "balibar" -> "balliab" - Fall", "caliri concatenated string * "allealf ws "alichia".