1-D Dynamic Programming Palindromes
526. Palindromic Substrings
You are given a string s. Return how many of its substrings are palindromes.
A substring is a block of letters that sit next to each other in s. A palindrome reads the same
forwards and backwards, such as "level" or "noon", and every single letter is one.
Substrings that start or end at different places count separately, even when they hold the same letters.
Example 1
Input: s = "abaab"
8Explanation: The five single letters are palindromes, and so are aa, aba and baab.
Example 2
Input: s = "aaa"
6Explanation: Each a counts, aa counts twice because it appears at two places, and aaa counts once.
Example 3
Input: s = "abc"
3Explanation: No two letters are equal, so only the three single letters are palindromes.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ s.length ≤ 3000sholds only lowercase English letters
Clarifying questions
What you would ask an interviewer before writing any code.