Palindrome Pairs (Codeforces 1046H)
Tags: Others, hashing

After learning a lot about space exploration, a little girl named Ana wants to change the subject.Ana is a girl who loves palindromes (string that can be read the same backwards as forward). She has learned how to check for a given string whether it's a palindrome or not, but soon she grew tired of this problem, so she came up with a more interesting one and she needs your help to solve it:You are given an array of strings which consist of only small letters of the alphabet. Your task is to find how many palindrome pairs are there in the array. A palindrome pair is a pair of strings such that the following condition holds: at least one permutation of the concatenation of the two strings is a palindrome. In other words, if you have two strings, let's say "aab" and "abcac", and you concatenate them into "aababcac", we have to check if there exists a permutation of this new string such that it is a palindrome (in this case there exists the permutation "aabccbaa"). Two pairs are considered different if the strings are located on different indices. The pair of strings with indices $$$(i,j)$$$ is considered the same as the pair $$$(j,i)$$$.

Input: The first line contains a positive integer $$$N$$$ ($$$1 \le N \le 100\,000$$$), representing the length of the input array.Eacg of the next $$$N$$$ lines contains a string (consisting of lowercase English letters from 'a' to 'z') — an element of the input array. The total number of characters in the input array will be less than $$$1\,000\,000$$$.

Output: Output one number, representing how many palindrome pairs there are in the array.

Note: The first example:  aa $$$+$$$ bb $$$\to$$$ abba. The second example:  aab $$$+$$$ abcac $$$=$$$ aababcac $$$\to$$$ aabccbaa aab $$$+$$$ aa $$$=$$$ aabaa abcac $$$+$$$ aa $$$=$$$ abcacaa $$$\to$$$ aacbcaa dffe $$$+$$$ ed $$$=$$$ dffeed $$$\to$$$ fdeedf dffe $$$+$$$ aade $$$=$$$ dffeaade $$$\to$$$ adfaafde ed $$$+$$$ aade $$$=$$$ edaade $$$\to$$$ aeddea 

Sample Inputs:
3
aa
bb
cd

6
aab
abcac
dffe
ed
aa
aade

Sample Outputs:
1

6

Solution (Python):
n = int(input())
string_count = {}
for _ in range(n):
    s = str(input())
    item_count = {}
    for (i, c) in enumerate(s):
        item_count[c] = item_count.get(c, 0) + 1
    s0 = []
    for x in 'abcdefghijklmnopqrstuvwxyz':
        if item_count.get(x, 0) % 2 == 1:
            s0.append(x)
    s1 = ''.join(s0)
    string_count[s1] = string_count.get(s1, 0) + 1
points = 0
for (a, x) in string_count.items():
    points += x * (x - 1) // 2
    for i in range(len(a)):
        points += x * string_count.get(a[:i] + a[i + 1:], 0)
print(points)

Solution (Python):
I = lambda : map(int, input().split())
n = int(input())
a = [0] * n
d = {}
for i in range(n):
    b = [0] * 26
    s = input()
    for j in s:
        b[ord(j) - 97] += 1
    odd = 0
    c = []
    for j in range(26):
        if b[j] % 2:
            odd += 1
            c.append(chr(j + 97))
    r = ''.join(c)
    d[r] = d.get(r, 0) + 1
    a[i] = odd
z = a.count(0)
k = a.count(1)
summ = z * k + z * (z - 1) // 2
if '' in d.keys():
    d.pop('')
for i in d.values():
    summ += i * (i - 1) // 2
for k in d.keys():
    for j in range(len(k)):
        r = k[:j] + k[j + 1:]
        try:
            summ += d[k] * d[r]
        except:
            continue
print(summ)

Solution (Python):
def lol(x):
    res = [0] * 26
    for i in x:
        res[ord(i) - 97] += 1
    s = ''
    for i in res:
        if i % 2 == 0:
            s += '0'
        else:
            s += '1'
    return s
n = int(input())
m = dict()
ans = 0
a = [lol(input()) for _ in range(n)]
for i in range(n):
    m[a[i]] = m.get(a[i], 0) + 1
for (k, v) in m.items():
    g = v - 1
    ans += (g + 1) * g // 2
set_lol = set(a)
ot = 0
for i in m.keys():
    for j in range(26):
        k = 0
        h = i[:j] + ('0' if i[j] == '1' else '1') + i[j + 1:]
        if h in set_lol:
            ot += m[h] * m[i]
print(ans + ot // 2)