Given a string s, count how many of its substrings are palindromes. A substring is a continuous part of the string. A palindrome reads the same from left to right and from right to left.
Substrings at different positions are counted separately, even if their text is the same.
Examples
Example 1:
Input: s = "madam"
Output: 7
Explanation: The palindromes are "m", "a", "d", "a", "m", "ada" and "madam". That is 7.
Example 2:
Input: s = "aab"
Output: 4
Explanation: The palindromes are "a", "a", "b" and "aa". That is 4.