For a palindrome string with even length, the number of occurrences of each character must be even. For a palindrome with odd length, the number of occurrences of each character must be even, except the character in the middle is odd. So you can maintain a frequency array to solve this problem.

Someone else asked this problem, seemed a bit strange. Anyway, the problem is pretty simple (or should I say mechanical):

1. Define the parity of a string $$$s$$$ (say $$$p(s)$$$) as the number of characters that have an odd number of occurrences in it. The cost for a substring $$$s[i..j]$$$ is $$$\lfloor p(s[i..j])/2 \rfloor$$$. When taking the sum of this over all substrings, note that it equals $$$\sum p(s[i..j])/2 - |\{(i, j) \mid p(s[i..j]) \text{ is odd}\}|/2$$$.
2. The first sum is easy — for each character from $$$a$$$ to $$$z$$$, find the number of substrings it contributes to — i.e., the number of substrings where it occurs an odd number of times. To do this, store positions of each character and use prefix/suffix sums for odd/even occurrences.
3. For the second part, note that if we extend a substring to the right by 1, then the parity of the substring changes. So, let's pair up all such substrings, and there will remain some suffix substrings, for which parity can be computed in $$$O(n)$$$ time by moving from right to left (use bitmasks and popcount). Since the total number of substrings is known, and the difference between the number of substrings with odd parity and even parity is known, we can count the number of substrings with odd parity by solving these two linear equations.