Count Every Palindromic Piece
Count the SUBSTRINGS of the string that read the same forwards and backwards. Substrings at different positions count separately even when identical.
aaa -> 6 a, a, a, aa, aa, aaa
abc -> 3 a, b, c
Every single character is a palindrome, so the answer is at least the length.
Checking every substring by reversing it is O(n^3). Two better routes, and both
are worth knowing.
The table:
pal[i][j] = s[i] == s[j] and (j - i < 2 or pal[i+1][j-1])
filled with i descending so the inner range is known, counting every true.
O(n^2) time and space.
Expanding around centres:
for each of the 2n - 1 centres:
grow outwards while the characters match, counting each match
The 2n - 1 is the part that gets missed: a palindrome's centre is either a
character, giving n centres, or the gap BETWEEN two characters, giving n - 1
more. Considering only single characters finds every odd-length palindrome and
misses every even one, so abba comes out as 4 instead of 6.
Centre expansion is O(n^2) time and O(1) space, which is why it is the version
to reach for once the table version is understood.