Count how many substrings of the string are palindromes. Substrings at different positions count separately, even if they look the same.
DSA Animator › DSA Revision › Strings › Palindromic Substrings
Remember: 2 n minus 1 centers cover odd and even palindromes. Each successful expansion is one more palindrome. The video solves Palindromic Substrings (LeetCode 647, Medium) with the Expand Around Center pattern from the Strings topic, and you can replay every step in the interactive Palindromic Substrings animation.
Count how many substrings of the string are palindromes. Substrings at different positions count separately, even if they look the same.
For a a a, there are 6: three single a, two a a, and one a a a.
Checking every substring for being a palindrome is O of n cubed.
Every palindrome has a center: either one character, or the gap between two characters. From each center, expand outward while both ends match, and count each successful expansion.
Center on the first a: count a. Center between the first two: count a a. Center on the middle a: count a, then expand and count a a a. Center between the last two: count a a. Center on the last a: count a. The total is 6.
In code, loop over 2 n minus 1 centers. Each center sets left and right, and expands while the characters match, adding 1 each time. It's O of n squared time and O of 1 space.
Remember: 2 n minus 1 centers cover odd and even palindromes. Each successful expansion is one more palindrome.