Palindromic Substrings
MediumDynamic Programming
You are given a string s. Return the number of contiguous substrings of s that are palindromes (read the same forwards and backwards).
Substrings are counted by position: two substrings with the same text but different start or end indices are counted separately. Every single character is a palindrome.
Example 1
- Input:
- s = "aabaa"
- Output:
- 9
- Explanation
- There are 5 single characters,
aatwice (indices 0-1 and 3-4),aba, and the whole stringaabaa: 5 + 2 + 1 + 1 = 9.
Example 2
- Input:
- s = "abba"
- Output:
- 6
- Explanation
- The four single characters,
bbin the middle, and the whole stringabba.
Example 3
- Input:
- s = "xyz"
- Output:
- 3
- Explanation
- No two neighbouring characters match, so only the three single characters count.
Constraints
- 1 ≤
s.length≤ 1000 sconsists of lowercase English letters