433. 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.
Constraints - `1 ≤ length ≤ 2000` - The string is lowercase English letters.
Input
One line containing the string.
Output
Print how many substrings are palindromes.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.