Question
Count Palindromic Substrings
You are given a string KaTeX can only parse string typed expression of length KaTeX can only parse string typed expression. Your task is to count the total number of substrings of KaTeX can only parse string typed expression that are palindromes. A substring is called a palindrome if it reads the same forward and backward.
Input
The first line contains a single integer KaTeX can only parse string typed expression — the length of the string.
The second line contains the string KaTeX can only parse string typed expression, consisting of lowercase English letters.
The second line contains the string KaTeX can only parse string typed expression, consisting of lowercase English letters.
Output
Print a single integer — the total number of palindromic substrings in KaTeX can only parse string typed expression.
Example
Input
5
ababa
Output
9
Explanation
All palindromic substrings are:
a, b, a, b, a (single characters)
aba (from index 0 to 2)
bab (from index 1 to 3)
aba (from index 2 to 4)
ababa (from index 0 to 4)
Total = 9 substrings.
5
ababa
Output
9
Explanation
All palindromic substrings are:
a, b, a, b, a (single characters)
aba (from index 0 to 2)
bab (from index 1 to 3)
aba (from index 2 to 4)
ababa (from index 0 to 4)
Total = 9 substrings.