StringDynamic Programming
Count how many substrings of the given string are palindromes. Substrings at different positions count separately, even if they contain the same letters.
Input
A single string of lowercase letters.
Output
Print the number of palindromic substrings.
Constraints
1 <= length <= 1000
Example 1
Input
abc
Output
3
Only the single letters a, b and c.
Example 2
Input
aaa
Output
6
a, a, a, aa, aa and aaa make 6.