Problem Statement

Palindrome Substrings Count A palindrome is a string that reads the same forwards and backwards, such as 121 or tacocat . A substring is a contiguous sequence of characters taken from inside a string. You are given a string s . Count how many distinct palindromic substrings s has. Two substrings are the same when their characters are the same; where they were taken from does not matter. So aa has the palindromic substrings a (at position 1), a (at position 2) and aa , but only two of them are distinct: a and aa . Characters are compared exactly, so A and a are different characters. Input Format A single line containing the string s . Output Format Print a single integer — the number of distinct palindromic substrings of s . Constraints 1 <= length(s) <= 1000 s consists of ASCII letters ( a - z , A - Z ) and digits ( 0 - 9 ) only; it contains no spaces. Examples Example 1 Input: aa Output: 2 Explanation: The palindromic substrings are a , a and aa . As strings there are only two d