Palindromic Substrings

Problem

Given a string s, count how many of its substrings are palindromes. Substrings at different positions count separately even if their text is identical.

• The string is up to 1,200 characters.
• s consists of lowercase English letters.

Examples

• s = "xyz" → 3. Only the three single characters.
• s = "ooo" → 6. "o" three times, "oo" twice, "ooo" once.
• s = "xyyx" → 6. Four singles plus "yy" and "xyyx".

Hints

1. Instead of testing every substring, think about where a palindrome's middle is.
2. If s[lo..hi] is a palindrome and s[lo-1] == s[hi+1], you have found another one. If they differ, can any wider substring around this centre be a palindrome?
3. Expand around all 2n-1 centres and count every successful expansion step; or fill dp[i][j] = s[i]==s[j] and dp[i+1][j-1] and count the true cells.