Alternate solution to https://www.interviewcake.com/question/permutation-palindrome

permutation-palindrome.py

# Interview Cake question #30
# Write an efficient function that checks whether any permutation of an input
# string is a palindrome.

from __future__ import print_function
# Strategy: XOR every character with each other. Runtime is O(n).
def is_palindrome(message):
    # Hash all the chars to prevent the result from colliding with
    # the ascii value of a different, but valid character when xoring.
    hashed_chars = map(hash, list(message))
    result = reduce(lambda a,x: a ^ x, hashed_chars)

    if len(message) % 2 == 0:
        # Check the length of the string. If it's even, everything should xor
        # out to zero
        return result == 0
    else:
        # If the string has an odd length, then there should only be one
        # element remaining
        return len([i for i in hashed_chars if i == result]) == 1

print(is_palindrome('civic')) # >>> True
print(is_palindrome('ivicc')) # >>> True
print(is_palindrome('civil')) # >>> False
print(is_palindrome('livci')) # >>> False