Palindrome Pairs (Codeforces 1045I)
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):
n1 = int(input())
u = {}
for i in range(n1):
    s = input()
    ld = {}
    for c in range(len(s)):
        if s[c] in ld:
            ld[s[c]] += 1
        else:
            ld[s[c]] = 1
    res = []
    for k in ld:
        if ld[k] % 2:
            res.append(k)
    res.sort()
    ans = ''
    for pro in range(len(res)):
        ans += res[pro]
    if ans in u:
        u[ans] += 1
    else:
        u[ans] = 1
res = 0
for ans in u:
    if len(ans) == 1:
        res += u[ans] * (u[ans] - 1) // 2
        if '' in u:
            res += u[ans] * u['']
    else:
        res += u[ans] * (u[ans] - 1) // 2
        for k in range(len(ans)):
            if ans[:k] + ans[k + 1:] in u:
                res += u[ans] * u[ans[:k] + ans[k + 1:]]
print(res)

Solution (Python):
n1 = int(input())
u = {}
for i in range(n1):
    s = input()
    ld = {}
    for c in range(len(s)):
        if s[c] in ld:
            ld[s[c]] += 1
        else:
            ld[s[c]] = 1
    result = []
    for k in ld:
        if ld[k] % 2:
            result.append(k)
    result.sort()
    answer = ''
    for p in range(len(result)):
        answer += result[p]
    if answer in u:
        u[answer] += 1
    else:
        u[answer] = 1
result = 0
for answer in u:
    if len(answer) == 1:
        result += u[answer] * (u[answer] - 1) // 2
        if '' in u:
            result += u[answer] * u['']
    else:
        result += u[answer] * (u[answer] - 1) // 2
        for k in range(len(answer)):
            if answer[:k] + answer[k + 1:] in u:
                result += u[answer] * u[answer[:k] + answer[k + 1:]]
print(result)

Solution (Python):
n1 = int(input())
u = {}
for i in range(n1):
    s = input()
    ld = {}
    for c in range(len(s)):
        if s[c] in ld:
            ld[s[c]] += 1
        else:
            ld[s[c]] = 1
    res = []
    for k in ld:
        if ld[k] % 2:
            res.append(k)
    res.sort()
    ans = ''
    for pro in range(len(res)):
        ans += res[pro]
    if ans in u:
        u[ans] += 1
    else:
        u[ans] = 1
res = 0
for ans in u:
    if len(ans) == 1:
        res += u[ans] * (u[ans] - 1) // 2
        if '' in u:
            res += u[ans] * u['']
    else:
        res += u[ans] * (u[ans] - 1) // 2
        for k in range(len(ans)):
            if ans[:k] + ans[k + 1:] in u:
                res += u[ans] * u[ans[:k] + ans[k + 1:]]
print(res)