I am trying to determine that whether any string is palindrome or not. For example, carrace should return true, since it can be rearranged to form racecar, which is a palindrome. daily should return false since there's no rearrangement that can form a palindrome. How can I solve this ?
Code:
string = 'racecar'
if string[::-1] == string:
print('palindrome')
Above code is working for single string , not for permutations
A string can be permuted to a palindrome if and only if there is at most one character that occurs an odd number of times.
from collections import Counter
def permute_palindrome(s):
return sum(1 for i in Counter(s).values() if i%2) <= 1
assert permute_palindrome('carrace')
assert not permute_palindrome('daily')
Detailed explanation:
Any palindrome has at most one character that occurs and odd number of times:
Consider any palindrome aabbcccbbaa
Note that by the definition of a palindrome any character on the left side is matched on the right side, so it forms a pair with this character. Counting characters in pairs will always lead to an even number (any multiple of 2 is an even number). The only exception to this is the middle character of an odd length string, this character is 'paired' with itself. So there is at most one character occuring an odd length number of times.
Any string that has at most one character occuring an odd number of times can be permuted to a palindrome:
We show a construction of a palindrome p in the following way. If there is a character occuring an odd number of times, add this to p. For any character occuring an even number of times, split this into two and add one part to the beginning of p and one part to the end of p. This results in a palindrome.
ex: aabbbbccd
p = d
p = ada
p = bbadabb
p = cbbadabbc