Palindromic Substrings
Palindromic Substrings is a medium 1-D Dynamic Programming problem from the Blind 75. The key pattern is expand around centre, and a good solution runs in O(n²) time.
Problem
Count all palindromic substrings, including identical text at different positions.
Examples
Example 1
Input
"ababa"Output
9Example 2
Input
"dog"Output
3Example 3
Input
"zzz"Output
6Approach
Expand from all 2n − 1 centres and count every successful step outward as one palindrome.
| Pattern | Expand around centre |
|---|---|
| Time | O(n²) |
| Space | O(1) |
Watch out for
Each single character counts as a palindrome.