medium
strings
dynamic-programming
Given a string s, return the number of palindromic substrings in it.
A substring is a contiguous sequence of characters within the string. Two substrings are counted separately if they start or end at different indices, even when they contain the same characters.
For example, in "aaa" the palindromic substrings are "a", "a", "a", "aa", "aa", and "aaa" — six in total.
Every single character is a palindrome, so the answer is always at least the length of the string.
Examples
Example 1
Input: s = "abc"
Output: 3
Example 2
Input: s = "aaa"
Output: 6
Example 3
Input: s = "aba"
Output: 4
Example 4
Input: s = "racecar"
Output: 10
Running will execute all 4 cases.