Problem Description

Given a string s, you need to find the length of the longest palindromic subsequence in it.

A subsequence is a sequence that can be derived from the original string by deleting some characters (or none) without changing the relative order of the remaining characters. Unlike a substring, the characters in a subsequence don't need to be consecutive in the original string.

A palindromic subsequence reads the same forwards and backwards.

For example:

• If s = "bbbab", the longest palindromic subsequence is "bbbb" with length 4
• If s = "cbbd", the longest palindromic subsequence is "bb" with length 2

The key insight is that we can use dynamic programming where dp[i][j] represents the length of the longest palindromic subsequence in the substring from index i to index j.

The recurrence relation works as follows:

• If the characters at positions i and j are the same (s[i] == s[j]), we can include both in our palindrome: dp[i][j] = dp[i+1][j-1] + 2
• If they're different, we take the maximum of either excluding the character at i or excluding the character at j: dp[i][j] = max(dp[i+1][j], dp[i][j-1])

The base case is that every single character is a palindrome of length 1, so dp[i][i] = 1.

The final answer is stored in dp[0][n-1], representing the longest palindromic subsequence for the entire string.

Intuition

The key observation is that a palindrome reads the same forwards and backwards. This means if we have a string and we're looking at characters at positions i and j, there are two scenarios:

1. If s[i] == s[j], these two characters can form the "outer layer" of a palindrome. Whatever palindrome exists between them (from i+1 to j-1), we can extend it by adding these matching characters on both ends, increasing the length by 2.

2. If s[i] != s[j], they can't both be part of the same palindrome. We must choose to either exclude s[i] or exclude s[j] from our palindrome, and we want whichever choice gives us a longer result.

This naturally leads to a recursive structure where we solve smaller subproblems first. To find the longest palindrome in a range [i, j], we need to know the answers for smaller ranges like [i+1, j-1], [i+1, j], and [i, j-1].

Think of it like peeling an onion - we start from the outer boundaries of our string and work our way inward, making optimal decisions at each step. When characters match, we "lock them in" as part of our palindrome and look at what's inside. When they don't match, we try both options of excluding one or the other.

The reason we iterate with i going backwards and j going forwards is to ensure that when we calculate dp[i][j], we've already computed all the smaller subproblems it depends on. This bottom-up approach builds from single characters (which are trivially palindromes of length 1) up to the entire string.

Learn more about Dynamic Programming patterns.

Solution Approach

We use dynamic programming to solve this problem. Create a 2D table dp where dp[i][j] represents the length of the longest palindromic subsequence in the substring from index i to index j.

Initialization:

• Create an n × n matrix filled with zeros, where n is the length of the string
• Set the diagonal elements dp[i][i] = 1 since every single character is a palindrome of length 1

Filling the DP Table: We need to fill the table in a specific order to ensure dependencies are met:

• Iterate j from 1 to n-1 (representing the ending position)
• For each j, iterate i from j-1 down to 0 (representing the starting position)
• This ensures that when computing dp[i][j], the values dp[i+1][j-1], dp[i+1][j], and dp[i][j-1] are already calculated

Recurrence Relation: For each pair (i, j):

• If s[i] == s[j]: These matching characters can form the outer boundary of a palindrome
  • dp[i][j] = dp[i+1][j-1] + 2
  • We add 2 to account for the two matching characters
• If s[i] != s[j]: The characters don't match, so we can't include both
  • dp[i][j] = max(dp[i+1][j], dp[i][j-1])
  • Take the maximum of either excluding character at position i or excluding character at position j

Final Answer: The value at dp[0][n-1] gives us the length of the longest palindromic subsequence for the entire string, as it represents the range from the first character to the last character.

The time complexity is O(n²) as we fill an n × n table, and the space complexity is also O(n²) for storing the DP table.

Example Walkthrough

Let's walk through the solution with s = "bbbab".

Step 1: Initialize the DP table Create a 5×5 table (since length = 5) and set diagonal to 1:

    0  1  2  3  4
    b  b  b  a  b
0 b [1  0  0  0  0]
1 b [0  1  0  0  0]
2 b [0  0  1  0  0]
3 a [0  0  0  1  0]
4 b [0  0  0  0  1]

Step 2: Fill the table systematically We process by increasing substring length, filling upper-right triangle:

For j=1, i=0: substring "bb"

• s[0]='b' == s[1]='b', so dp[0][1] = dp[1][0] + 2 = 0 + 2 = 2

For j=2, i=1: substring "bb" (index 1-2)

• s[1]='b' == s[2]='b', so dp[1][2] = dp[2][1] + 2 = 0 + 2 = 2

For j=2, i=0: substring "bbb"

• s[0]='b' == s[2]='b', so dp[0][2] = dp[1][1] + 2 = 1 + 2 = 3

For j=3, i=2: substring "ba"

• s[2]='b' != s[3]='a', so dp[2][3] = max(dp[3][3], dp[2][2]) = max(1, 1) = 1

For j=3, i=1: substring "bba"

• s[1]='b' != s[3]='a', so dp[1][3] = max(dp[2][3], dp[1][2]) = max(1, 2) = 2

For j=3, i=0: substring "bbba"

• s[0]='b' != s[3]='a', so dp[0][3] = max(dp[1][3], dp[0][2]) = max(2, 3) = 3

For j=4, i=3: substring "ab"

• s[3]='a' != s[4]='b', so dp[3][4] = max(dp[4][4], dp[3][3]) = max(1, 1) = 1

For j=4, i=2: substring "bab"

• s[2]='b' == s[4]='b', so dp[2][4] = dp[3][3] + 2 = 1 + 2 = 3

For j=4, i=1: substring "bbab"

• s[1]='b' == s[4]='b', so dp[1][4] = dp[2][3] + 2 = 1 + 2 = 3

For j=4, i=0: substring "bbbab" (entire string)

• s[0]='b' == s[4]='b', so dp[0][4] = dp[1][3] + 2 = 2 + 2 = 4

Final DP table:

    0  1  2  3  4
    b  b  b  a  b
0 b [1  2  3  3  4]
1 b [0  1  2  2  3]
2 b [0  0  1  1  3]
3 a [0  0  0  1  1]
4 b [0  0  0  0  1]

Result: dp[0][4] = 4, meaning the longest palindromic subsequence has length 4. The subsequence is "bbbb" (taking all 'b' characters and skipping the 'a').

Solution Implementation

Time and Space Complexity

The time complexity is O(n^2), where n is the length of the string s. This is because we have two nested loops - the outer loop iterates through all possible lengths (from 1 to n-1), and the inner loop iterates through all possible starting positions for each length. The total number of subproblems we need to solve is approximately n * (n-1) / 2, which gives us O(n^2) operations.

The space complexity is O(n^2), where n is the length of the string s. We create a 2D DP table dp of size n × n to store the longest palindromic subsequence length for each substring s[i:j+1]. Each cell in the table stores an integer value, and we have n^2 cells in total, resulting in O(n^2) space usage.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Iteration Order

Pitfall: A common mistake is iterating through the DP table in the wrong order, such as iterating i from 0 to n-1 instead of from j-1 down to 0. This causes the algorithm to access uninitialized values.

# WRONG: This iteration order doesn't guarantee subproblems are solved first
for i in range(n):
    for j in range(i + 1, n):
        # dp[i+1][j-1] might not be computed yet!
        if s[i] == s[j]:
            dp[i][j] = dp[i + 1][j - 1] + 2

Solution: Always iterate j from left to right (1 to n-1), and for each j, iterate i from right to left (j-1 down to 0). This ensures that when computing dp[i][j], all required subproblems dp[i+1][j-1], dp[i+1][j], and dp[i][j-1] are already computed.

# CORRECT: Proper iteration order
for j in range(1, n):
    for i in range(j - 1, -1, -1):
        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])

2. Forgetting Base Cases

Pitfall: Not initializing the diagonal elements dp[i][i] = 1, which leads to incorrect results since single characters are palindromes of length 1.

# WRONG: Missing base case initialization
dp = [[0] * n for _ in range(n)]
# Forgot to set dp[i][i] = 1

Solution: Always initialize the diagonal before filling the rest of the table:

# CORRECT: Initialize base cases
for i in range(n):
    dp[i][i] = 1

3. Index Out of Bounds When i+1 > j-1

Pitfall: When s[i] == s[j] and the substring length is 2 (i.e., j = i + 1), accessing dp[i+1][j-1] actually means accessing dp[i+1][i], which crosses the diagonal. While this typically returns 0 (which is correct for an empty substring), it's conceptually confusing.

Solution: Either ensure your DP table is initialized with zeros (which handles this case automatically), or explicitly check for this condition:

# More explicit handling (optional)
if s[i] == s[j]:
    if i + 1 <= j - 1:
        dp[i][j] = dp[i + 1][j - 1] + 2
    else:
        dp[i][j] = 2  # Two matching characters with nothing in between

4. Space Optimization Confusion

Pitfall: Attempting to optimize space by using a 1D array without carefully considering dependencies can lead to incorrect results, as this problem requires information from multiple previous rows/columns.

Solution: While space optimization to O(n) is possible using two arrays or careful in-place updates, stick with the 2D approach initially for clarity. The space optimization requires tracking values carefully:

# Space-optimized version (more complex but uses O(n) space)
def longestPalindromeSubseq_optimized(s: str) -> int:
    n = len(s)
    dp = [1] * n  # Current row
  
    for j in range(1, n):
        prev = dp[:]  # Previous state
        dp[j] = 1  # Reset diagonal
        for i in range(j - 1, -1, -1):
            if s[i] == s[j]:
                dp[i] = (prev[i + 1] if i + 1 < j else 0) + 2
            else:
                dp[i] = max(dp[i + 1], prev[i])
  
    return dp[0]