Piet Souris wrote:Suppose we have a string of an even number of characters. And suppose we can form a palindrome.
What does that mean? Every character in the left half must also be present in the right half.
If we thus make a frequency table of all the characters, we see that each frequency must be even.
If, on the other hand, we have an uneven number of characters in the string, then we have some
character in the middle. For the left haf characters we have the same situation as before, so
all the characters have an even frequency, except for one character, which has an uneven frequency and must be in the middle.
Now, how many palindromes do we have? Well, I've written quite some code about something similar, in the 'programming diversion' forum, 2nd page. The way to calculate that number is a well known formula from the combinatorics: given W white balls, R red and G green, how many permutations do we have? And in this case: divide the answer by 2. (edit: or each frequency by 2 before calculating the answer? ;))