How to count the possible palindromes that can be generated using the letters of the input string ?
1 <= string_size() <= 10000.

Have a look at this.

string = “abca”
output = 6
palindromes = { a , b , c , aa , aba , aca }

Please, see the example for clarification.

Palindrome string is a string which remains unchanged when it is reversed.
So, considering the program that gives the number of all possible palindromes.
First case – Number of characters is odd.
any string of only one character is trivially a palindrome string.
now for a string of length=2k+1 k is a natural number
fix the middle element and then take two --First array will have all the elements before the middle element.
Second array will have all the elements after the middle element.
Clearly the element and the order of elements in the first array will uniquely determine the second array.
Second case – Number of characters is even.
min length of a palindrome string with even number of elements is two.
Let the number of elements=2k k is a natural number.
Then take two arrays the first array having the first k elements and the second array having the last k elements.
In this case also the first array uniquely determines the second array.

So, basically now the problem reduces to finding the number of ways a k length array can be constructed where 1<=k<=500.
And so we are precisely done!!

Try it out.
It will give the same answers!!