Palindromic DP

What is this?

Palindromes have a recursive shape that hands you the recurrence: a string is a palindrome exactly when its two ends match and everything between them is a palindrome. That single sentence turns into dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1], and the whole chapter is consequences of it.

The catch is the fill order. dp[i][j] depends on dp[i+1][j-1] — a shorter interval sitting inside it — so the table must be filled from short intervals outward, never in plain row-major order.

💡 Fun fact: Palindromic Substrings has a solution that beats the DP table on space and is easier to write: expand around every centre. A string of length n has 2n − 1 centres — n single characters and n − 1 gaps between them — and expanding outward from each while the characters match counts every palindrome exactly once. O(n²) time like the table, but O(1) space instead of O(n²). It is one of the few cases where the non-DP answer is strictly better and still easy to justify.

🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: the state is an interval, and the recurrence peels characters off both ends. Fill the table by increasing interval length so that the inner substring is always already computed.

1. Two recurrences, one shape

Is s[i..j] a palindrome?

dp[i][j] = s[i] == s[j] and (j - i < 2 or dp[i+1][j-1])

The j - i < 2 clause covers the two base cases at once — a single character is a palindrome, and two equal characters are too — without needing separate initialisation loops.

How long is the longest palindromic subsequence of s[i..j]?

if s[i] == s[j]:  dp[i][j] = dp[i+1][j-1] + 2
else:             dp[i][j] = max(dp[i+1][j], dp[i][j-1])

Note the difference from substrings: a subsequence may skip characters, so when the ends disagree you drop one and take the better of the two options rather than failing outright. That single else branch is the whole distinction between the two problems, and confusing them is the most common error in this chapter.

2. Fill order

Both recurrences read a shorter interval, so either iterate i downward while j runs upward from i:

for i in range(n - 1, -1, -1):
    for j in range(i, n):
        ...

or iterate explicitly by length. The downward i loop works because dp[i+1][...] was computed on the previous outer iteration. Filling in the natural top-to-bottom, left-to-right order reads cells that are still zero and produces answers that look plausible and are wrong.

3. Expand around centres

For counting substrings, skip the table entirely:

count = 0
for centre in range(2 * n - 1):
    left, right = centre // 2, centre // 2 + centre % 2
    while left >= 0 and right < n and s[left] == s[right]:
        count += 1
        left -= 1; right += 1

The index arithmetic handles odd-length centres (a character) and even-length centres (a gap) uniformly, which is why there is one loop rather than two.

4. A 30-second worked example

s = "bbbab", longest palindromic subsequence:

        b   b   b   a   b        (j →)
   b    1   2   3   3   4
   b        1   2   2   3
   b            1   1   3
   a                1   1
   b                    1
   (i ↓)

dp[2][4]: s[2]='b', s[4]='b' → equal → dp[3][3] + 2 = 1 + 2 = 3
dp[0][4]: s[0]='b', s[4]='b' → equal → dp[1][3] + 2 = 2 + 2 = 4  ✅

The answer is 4 — "bbbb" — obtained by skipping the 'a'. Every cell was computed from one strictly shorter interval, which is exactly what the fill order guarantees.

5. Where you'll actually meet this

• Bioinformatics. Palindromic sequences in DNA mark restriction sites, and the interval DP here is the same machinery as sequence alignment.
• Text processing. Longest common subsequence, edit distance and diff are all interval or two-sequence DP with different recurrences.
• Compression. Detecting repeated and mirrored structure to encode it once.
• Compilers. Optimal parenthesisation of expressions and matrix chains is interval DP with a min over split points.
• Data validation. Palindrome checks appear in checksum and identifier schemes.

6. Problems in this chapter

▶ Palindromic Substrings

Count palindromic substrings. Expand around all 2n − 1 centres for O(1) space, or fill the boolean table and sum the true cells.
Pattern: centre expansion (or interval DP). Target: O(n²) time, O(1) space.

▶ Longest Palindromic Subsequence

Length of the longest palindromic subsequence. Interval DP where mismatched ends drop one side and take the better.
Pattern: interval DP with a skip branch. Target: O(n²) time, O(n²) space (or O(n) rolled).

7. Common pitfalls 🚫

• Confusing substring with subsequence. Substrings are contiguous and fail on a mismatch; subsequences may skip and take the better side.
• Filling the table row-major. The inner interval must be computed first — iterate i downward.
• Missing the j - i < 2 base case. Without it, two-character palindromes read an inverted, uninitialised cell.
• Using the DP table when centre expansion is better. For counting substrings it is the same time and far less space.
• Getting the centre arithmetic wrong. There are 2n − 1 centres, not n; forgetting the even centres loses every even-length palindrome.
• Returning the count instead of the length (or the reverse) — the two problems here differ in what they report.
• Assuming the longest subsequence is contiguous. In "bbbab" it is not.

8. Key takeaways

1. The state is an interval, and the recurrence peels both ends.
2. Ends match → recurse inward. Ends differ → substrings fail, subsequences skip.
3. Fill by increasing length. The commonest bug in interval DP is the loop direction.
4. j - i < 2 folds both base cases into the recurrence.
5. Centre expansion beats the table for counting substrings, at O(1) space.
6. There are 2n − 1 centres, half of them between characters.
7. Why interviewers like it: two problems that look nearly identical need genuinely different recurrences, so it is an efficient test of whether you derived the recurrence or recalled one.

Order: Palindromic Substrings → Longest Palindromic Subsequence.