What is the best algorithm to find whether an anagram is of a palindrome?

Question

In this problem we consider only strings of lower-case English letters (a-z).

A string is a palindrome if it has exactly the same sequence of characters when traversed left-to-right as right-to-left. For example, the following strings are palindromes:

"kayak"

"codilitytilidoc"

"neveroddoreven"

A string A is an anagram of a string B if it consists of exactly the same characters, but possibly in another order. For example, the following strings are each other's anagrams:

A="mary" B="army" A="rocketboys" B="octobersky" A="codility" B="codility"

Write a function

int isAnagramOfPalindrome(String S);

which returns 1 if the string s is a anagram of some palindrome, or returns 0 otherwise.

For example your function should return 1 for the argument "dooernedeevrvn", because it is an anagram of a palindrome "neveroddoreven". For argument "aabcba", your function should return 0.

Answer 1

'Algorithm' would be too big word for it.

You can construct a palindrome from the given character set if each character occurs in that set even number of times (with possible exception of one character).
For any other set, you can easily show that no palindrome exists.

Proof is simple in both cases, but let me know if that wasn't clear.

Answer 2

In a palindrome, every character must have a copy of itself, a "twin", on the other side of the string, except in the case of the middle letter, which can act as its own twin.

The algorithm you seek would create a length-26 array, one for each lowercase letter, and start counting the characters in the string, placing the quantity of character n at index n of the array. Then, it would pass through the array and count the number of characters with an odd quantity (because one letter there does not have a twin). If this number is 0 or 1, place that single odd letter in the center, and a palindrome is easily generated. Else, it's impossible to generate one, because two or more letters with no twins exist, and they can't both be in the center.