516. Longest Palindromic Subsequence

Problem¶

Given a nonempty string s, return the maximum length of a palindromic subsequence. Characters may be deleted but cannot be reordered.

Input:  s = "bbbab"
Choice: "bbbb"
Output: 4

Key trick¶

Use interval dynamic programming: if the endpoints match, include both; otherwise discard the endpoint whose removal gives the better result.

Trap¶

• Confusing a subsequence with a contiguous substring.
• Greedily matching characters without considering both endpoint removals.
• Overwriting DP states before saving the previous diagonal value.

Why is it interesting?¶

It is a classic interval DP whose \(O(n^2)\) table can be compressed to one dimension.

Python solution¶

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        dp = [1] * n

        # dp[j] becomes the answer for s[i:j + 1].
        for i in range(n - 2, -1, -1):
            prev = 0

            for j in range(i + 1, n):
                # Preserve dp[i + 1][j] before overwriting it.
                old = dp[j]

                if s[i] == s[j]:
                    # prev is dp[i + 1][j - 1].
                    dp[j] = prev + 2
                else:
                    # dp[j] is dp[i + 1][j], and dp[j - 1] is dp[i][j - 1].
                    dp[j] = max(dp[j], dp[j - 1])

                prev = old

        return dp[-1]

Time complexity: \(O(n^2)\).

Space complexity: \(O(n)\).

Comment on my solution¶

Not provided.

# Ideas:
# - Deleting elements <-> keeping elements
# - how can I partionne the string into indepent sub problems?
# - x <pal> x => x<pal>x palindrome
# - a or aa or aba smallest palindrome
# - bbb a b -> bbbb
# - bbb a c -> bbb
# - c bb d  -> bb
# - c bb d bb e  -> bbbb


class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:

Extra¶

Complement on the solution and interval DP¶

It's not clear to me.

Can you explain me the solution with more details, especially the 2 DP first, I don't see what's going on.

Can you tell me what is interval DP, and how to recognize when and how to use it on a problem.

The missing idea is that we solve the problem for every substring interval, not directly for the whole string.

Start with 2D dynamic programming¶

For each pair of indices l and r, define:

For example, if s = "cbbd":

• dp[1][2] concerns "bb", so its value is 2.
• dp[0][2] concerns "cbb", so its value is 2.
• dp[0][3] concerns "cbbd", which is the final answer.

The key is to examine the two characters at the boundaries of an interval.

Case 1: The boundary characters match¶

If s[l] == s[r], they can become the two ends of a palindrome:

Example:

interval: "a bcb a"
           ^     ^

inner palindrome: "bcb"
result:           "abcba"

The matching endpoints contribute 2, and the best palindrome inside contributes the rest.

Case 2: The boundary characters do not match¶

If s[l] != s[r], they cannot both be the endpoints of the same palindrome. We try removing either one:

For "cbbd":

Remove "c": consider "bbd"
Remove "d": consider "cbb"

Take the better result.

Base case¶

An interval containing one character is already a palindrome of length 1:

Empty intervals conceptually have length 0. This matters for two equal adjacent characters:

Why the filling order matters¶

To calculate dp[l][r], we may need:

• dp[l+1][r-1]
• dp[l+1][r]
• dp[l][r-1]

These all represent shorter intervals. Therefore, shorter intervals must be computed before longer ones.

One natural order is increasing interval length:

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        dp = [[0] * n for _ in range(n)]

        # Every single character is a palindrome.
        for i in range(n):
            dp[i][i] = 1

        # Compute intervals from shortest to longest.
        for length in range(2, n + 1):
            for l in range(n - length + 1):
                r = l + length - 1

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

        return dp[0][n - 1]

The access dp[l + 1][r - 1] is safe for an interval of length 2: it accesses the unused lower half of the table, which remains 0.

Time complexity: \(O(n^2)\).

Space complexity: \(O(n^2)\).

Example table construction¶

For s = "cbbd":

Intervals of length 1¶

"c" -> 1
"b" -> 1
"b" -> 1
"d" -> 1

Intervals of length 2¶

"cb" -> 1
"bb" -> 2
"bd" -> 1

Intervals of length 3¶

"cbb" -> 2
"bbd" -> 2

Interval of length 4¶

"cbbd" -> max("bbd", "cbb") -> 2

The final answer is dp[0][3] = 2.

What is interval DP?¶

Interval DP is dynamic programming where each state represents the answer for a contiguous interval:

The transition reduces the interval by:

• Removing the left endpoint.
• Removing the right endpoint.
• Removing both endpoints.
• Splitting the interval at some position.

Typical state dependencies look like:

Or, for problems that split an interval:

How to recognize interval DP¶

Look for these signs:

• The problem asks about a string, array, or sequence.
• A subproblem can be described by left and right boundaries.
• Decisions involve the first or last element of the current range.
• Removing boundaries produces a smaller version of the same problem.
• The answer for a range can be built from answers for smaller ranges.
• The problem asks for an optimal way to combine, remove, partition, or match elements.

Common interval DP problems include:

• Longest palindromic subsequence.
• Minimum insertions to make a string a palindrome.
• Matrix chain multiplication.
• Burst balloons.
• Optimal polygon triangulation.
• Minimum cost to merge intervals.

A useful thought process is:

1. Define what dp[l][r] means.
2. Decide what happens at the two boundaries.
3. Express the answer using shorter intervals.
4. Identify the smallest intervals as base cases.
5. Fill intervals from shortest to longest.

Why can the 2D table become 1D?¶

In the recurrence, row l only needs values from:

• The previous row l + 1.
• The current row l.

For the mismatch case:

In a one-dimensional array:

• dp[r] before updating is dp[l+1][r].
• dp[r - 1] after updating is dp[l][r-1].

For the matching case, we also need dp[l+1][r-1]. A variable named prev saves that old diagonal value.

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        dp = [1] * n

        # Move the left boundary backward.
        for l in range(n - 2, -1, -1):
            # Represents the empty interval before the first update.
            prev = 0

            # Move the right boundary forward.
            for r in range(l + 1, n):
                # Before updating, dp[r] is dp[l + 1][r].
                old = dp[r]

                if s[l] == s[r]:
                    # prev is the old dp[l + 1][r - 1].
                    dp[r] = prev + 2
                else:
                    # dp[r] is dp[l + 1][r].
                    # dp[r - 1] is the new dp[l][r - 1].
                    dp[r] = max(dp[r], dp[r - 1])

                # Save the old value as the diagonal for the next r.
                prev = old

        return dp[-1]

The three important values during an update are:

That correspondence is the entire trick behind the space optimization.

Time complexity: \(O(n^2)\).

Space complexity: \(O(n)\).

The safest interview approach is to derive and explain the 2D recurrence first, then present the 1D optimization only after the table is clear.