165. Palindromic Substrings

Medium · Dynamic Programming

Given a string, find all distinct palindromic substrings. A palindrome reads the same forwards and backwards. Return the count of all distinct palindromic substrings, including single characters.

For example, in the string "ababa", the palindromic substrings are "a", "b", "aba", "bab", and "ababa", giving a count of 5 distinct palindromes.

Examples

Example 1
Input: "abc"
Output: 3
Explanation: The palindromic substrings are "a", "b", and "c". Each single character is a palindrome, and there are no multi-character palindromes.
Example 2
Input: "ababa"
Output: 5
Explanation: The palindromic substrings are "a", "b", "aba", "bab", and "ababa". Note that "a" and "b" appear multiple times but are counted only once.

Constraints