Palindrome DP¶
Also known as: Palindromic Substrings DP, Expand Around Center
A string is a palindrome if its ends match and the string inside them is a palindrome — which is a recursive definition begging for a table. But there's a rival approach worth knowing: stand at each character (and each gap) and expand outward while the ends match. Same O(n²) time, but O(1) space and far less code.
Before you start¶
What 'solved properly' looks like
Target: O(n²). If your solution is slower than that, you've found a solution but not this pattern — the judge says "Accepted" either way, so treat this as your real benchmark.
The idea¶
You build a 2-D table where cell (i, j) is true if the substring from i to j is a palindrome. The recurrence is simple: s[i] == s[j] and (j - i <= 2 or dp[i+1][j-1]). Fill the table by substring length (short to long) so shorter substrings are computed before longer ones that depend on them. The alternative — expand around each center — skips the table entirely and is often the better submission.
Why it matters: It's a rare case where the DP formulation and a simpler non-DP approach are equally valid, which makes it the best place on the whole roadmap to practise choosing rather than reflexively reaching. Understanding both and picking deliberately is the lesson.
When to reach for it¶
Reach for it when you need the "longest palindromic substring", "longest palindromic subsequence", or "count the palindromic substrings." These are the problems where the inner-outer recurrence is most natural.
When not to use it
Expand-around-center is usually the better submission (same time, O(1) space, simpler) — build the DP table to understand it, then pick deliberately. Manacher's algorithm gets it to O(n) but is almost never required; reaching for it is a red flag, not a badge.
Practice set¶
Work these top to bottom. The time-box is a cue to pause and re-read the triggers above if you're still stuck when it passes — not a deadline to race. Getting unstuck by stepping back is the skill being trained.
| # | Problem | Where | Difficulty | Time-box | Role |
|---|---|---|---|---|---|
| 1 | Longest Palindromic Substring | LeetCode | Medium | 25 mins | teaching |
| 2 | Palindromic Substrings | LeetCode | Medium | 20 mins | teaching |
| 3 | Longest Palindromic Subsequence | LeetCode | Medium | 30 mins | consolidation |
| 4 | Palindrome Partitioning II | LeetCode | Hard | 40 mins | challenge |
Already know this? Test out.
If you can solve Palindrome Partitioning II cleanly in one sitting — computing the minimum cuts via DP — you already own this pattern, so move on to the next one. If it tangles you up, that's your signal to work the set from the top instead of skipping.