Palindromic Substrings
Given a string s, count how many of its substrings are palindromes.
A substring is a contiguous slice of the string; a subsequence, by contrast, may skip characters. A palindrome reads the same forwards and backwards. Identical substrings sitting at different positions count separately.
Input & Output
Input
s — the input string
Output
the number of palindromic substrings in s
Example
Input
s = "aaa"
Output
6
Explanation
The single characters "a" at indices 0, 1, and 2 give three, the substrings "aa" at indices 0-1 and 1-2 give two more, and "aaa" itself gives the sixth. The repeated "a" and "aa" count separately because they sit at different positions.
Example
Input
s = "abcba"
Output
7
Explanation
The five single characters are each a palindrome, and "bcb" at indices 1-3 and "abcba" at indices 0-4 add two more.
Constraints
1 <= s.length <= 1000sconsists of lowercase English letters