Count every palindromic substring

Question

Given a string, count how many of its contiguous substrings are palindromes. Every single character counts as a palindrome, and different positions count separately even if the text is identical.

"abc"  -> 3     # "a", "b", "c"
"aaa"  -> 6     # "a","a","a","aa","aa","aaa"

Return the total count in $O(n^2)$ time. The brute force checks all $O(n^2)$ substrings at $O(n)$ each, which is $O(n^3)$ ; do better.

Accepted Answer

Every palindromic substring has a center: a single character (odd length) or the gap between two characters (even length), 2n - 1 centers in all. Fix a center and expand outward while the two frontier characters match. Each successful expansion step corresponds to exactly one distinct palindrome, so instead of remembering the widest interval, you increment a counter on every match. Tracing "aaa": the three odd centers contribute 1 + 2 + 1 = 4 (the middle character reaches all the way out to "aaa"), and the two even centers between adjacent a's contribute 1 + 1 = 2, for a total of 6. That matc…

Count every palindromic substring

Your answer

More Coding questions