Introduction

The longest palindromic subsequence problem asks for the maximum-length subsequence of a string that reads the same forward and backward. The standard dynamic programming solution uses O(n^2) memory, but if you only need the length and not the full reconstruction, you can reduce the memory requirement to O(n) while keeping the same O(n^2) time complexity.

The Standard DP Recurrence

For a string s, define dp[i][j] as the length of the longest palindromic subsequence inside the substring from index i to index j.

The recurrence is:

• if s[i] == s[j], then dp[i][j] = dp[i + 1][j - 1] + 2
• otherwise, dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])

The base case is dp[i][i] = 1, because a single character is always a palindrome of length 1.

That solution is correct, but the full table stores n * n entries. For long strings, memory becomes the real cost.

Why the Memory Can Be Reduced

Notice which values each state needs:

• the cell directly below
• the cell to the left
• the diagonal cell from the previous row

That means you do not need the entire 2D table at once. You only need the current row plus enough information to remember the old diagonal value before it gets overwritten.

This leads to a 1D DP array.

A Space-Optimized 1D Solution

1def longest_palindrome_subsequence_length(s: str) -> int:
2    n = len(s)
3    if n == 0:
4        return 0
5
6    dp = [0] * n
7
8    for i in range(n - 1, -1, -1):
9        dp[i] = 1
10        prev_diag = 0
11
12        for j in range(i + 1, n):
13            old_dp_j = dp[j]
14
15            if s[i] == s[j]:
16                dp[j] = prev_diag + 2
17            else:
18                dp[j] = max(dp[j], dp[j - 1])
19
20            prev_diag = old_dp_j
21
22    return dp[n - 1]
23
24
25print(longest_palindrome_subsequence_length("bbbab"))
26print(longest_palindrome_subsequence_length("cbbd"))

Output:

4
2

For "bbbab", one longest palindromic subsequence is "bbbb", so the length is 4.

What prev_diag Represents

The trickiest part of the 1D approach is the variable often called prev_diag.

When the inner loop is at indices i and j:

• 'dp[j] still represents the old value for dp[i + 1][j]'
• 'dp[j - 1] already represents the new value for dp[i][j - 1]'
• 'prev_diag stores the old value for dp[i + 1][j - 1]'

That is exactly the data the recurrence needs.

The update order matters. If you loop in the wrong direction or overwrite dp[j] too early, you destroy the values needed for later cells.

Complexity and Tradeoffs

The optimized version still examines essentially every i, j pair, so the time complexity remains O(n^2).

The benefit is memory:

• 2D DP uses O(n^2) space
• 1D DP uses O(n) space

That difference matters when the input string is large.

The tradeoff is that reconstruction becomes harder. The 1D DP array is great for computing the length, but it does not preserve enough information to rebuild the actual subsequence without extra storage or a second pass.

Subsequence vs Substring

This problem is about subsequences, not substrings.

A subsequence can skip characters while preserving order. For example, in "character", a palindromic subsequence can skip several characters and still be valid.

A substring must remain contiguous.

Mixing those two problems leads to incorrect recurrences and wrong answers.

Common Pitfalls

The biggest mistake is iterating in the wrong order. The 1D DP method depends on filling i from right to left and j from left to right after i.

Another common bug is forgetting what prev_diag means. It must hold the old diagonal value before dp[j] gets overwritten.

Developers also sometimes expect the 1D array to reconstruct the full subsequence automatically. It usually cannot do that by itself; the memory optimization mainly gives you the length.

Finally, do not confuse longest palindromic subsequence with longest palindromic substring. They are different problems with different algorithms.

Summary

• The classic LPS recurrence is still the foundation of the memory-optimized solution.
• You can reduce memory from O(n^2) to O(n) if you only need the length.
• The 1D approach works by carefully reusing old row values and one saved diagonal value.
• Time complexity stays O(n^2).
• The optimized method is excellent for length calculation, but full sequence reconstruction needs additional information.