Palindromic DP

What is this?

A palindrome reads the same forwards and backwards, which gives it a tidy inside-out structure: a stretch of text is a palindrome only if its two ends match and the smaller stretch inside it is one too. Palindromic DP uses that fact by solving the short pieces first and remembering them, so each longer piece just checks its ends and looks up the inner answer it already has. It is like peeling outward from the middle, never re-checking a center you have already grown from.

💡 Fun fact: A naive palindrome search can be quadratic, but Manacher's algorithm finds the longest palindromic substring in linear time by reusing mirror information across centers — a rare case where the clever trick brings an O(n^2) problem all the way down to O(n).

🔓 The 1 problem in this chapter is free. Sign in with Google or Microsoft to start solving.

Core idea: A palindrome reads the same forwards and backwards, which gives it a recursive inside-out structure: s[i..j] is a palindrome iff its ends match and the span inside it is too. That single fact powers two techniques — a DP table filled by increasing length, or an O(1)-space expand-around-center scan.

Two ways to exploit symmetry

The DP makes the inside-out dependency explicit (you must compute shorter spans before longer ones); expand-around-center is the same idea run from the middle of each potential palindrome.

The problem

• Longest Palindromic Substring — find the longest contiguous palindrome via the dp table (fill by length) or expand-around-center (handle both odd and even centers); Manacher's gives O(n) for the curious.

Key takeaways

• Palindromes are inside-out — ends match and the interior is a palindrome.
• DP fills by length because dp[i][j] depends on the shorter dp[i+1][j-1].
• Expand-around-center is the clean O(1)-space default — remember the even-length centers.
• Why interviewers love it: it tests recognizing recursive symmetry and handling the odd/even gotcha.

Problem: Longest Palindromic Substring.