Expand Around Centre vs DP
Use expansion for the longest palindromic substring, because it gets the same O(n squared) time in O(1) space and is shorter to write. Use the DP table when later work needs to ask repeatedly whether a given substring is a palindrome.
Both find palindromes in O(n squared) and they differ in what they leave behind. Expanding from each centre keeps nothing but the best answer so far. The DP table fills an n by n grid of is this substring a palindrome, which costs memory and makes every later check free, and that matters when another algorithm sits on top.
Side by side
| Dimension | Expand around centre | DP table |
|---|---|---|
| Time | O(n squared) | O(n squared) |
| Space | O(1) | O(n squared), or O(n) with one row |
| Leaves behind | Only the answer | Every substring answered |
| Centres to consider | 2n - 1, odd and even lengths | Handled by substring length in the loop |
| Code length | A helper and one loop | Two nested loops and a base case |
| Counting all palindromic substrings | Works, count each successful expansion | Works, count the true cells |
When to pick each
Expand around centre
- Longest palindromic substring on its own, where the O(1) space is free and the code is half the length.
- Counting palindromic substrings, where each expansion step that succeeds is one more palindrome.
DP table
- Palindrome partitioning, where backtracking asks is s[i..j] a palindrome thousands of times and the table makes each check O(1).
- Minimum cuts to partition into palindromes, which is a second DP layered on the first.
- Any problem where the palindrome test is inside another loop rather than being the answer.
Expanding from single characters only. Every even-length palindrome has its centre between two characters, so abba is missed entirely by a loop that treats each index as one centre. There are 2n - 1 centres, not n, and the usual fix is to call the expansion helper twice per index, once with both pointers at i and once with them at i and i + 1.
Questions people ask
Is there anything faster than O(n squared)?
Manacher's algorithm, which finds the longest palindromic substring in O(n) by reusing the radii it has already computed around a mirror centre. It is rarely expected in an interview, and the honest answer is to name it, say expansion is O(n squared) and offer Manacher as the linear option if they want it.
Why does the DP table fill by substring length?
Because s[i..j] is a palindrome when its ends match and s[i+1..j-1] already is, so the shorter substring has to be computed first. Looping by length guarantees that order. The same reason explains the two base cases: a single character is always a palindrome and a pair is one when the characters match.
Can the DP table be reduced to one dimension?
For some questions, yes. Each row only ever reads the row below it, so a single array plus careful iteration order suffices when you need only the counts or the best length. If a later algorithm needs to query arbitrary substrings, the full table is the point and shrinking it defeats the purpose.