Longest Palindromic Subsequence

Medium Subject: 2-D Dynamic Programming

Time Complexity

O(N^2)

Space Complexity

O(N^2)

Problem Description

Problem Statement

Given a string s, find the longest palindromic subsequence's length in s.

Example 1:

Input: s = "bbbab"
Output: 4
Explanation: One possible longest palindromic subsequence is "bbbb".

Optimal Solution

Python

Approach: 2-D DP

We use a 2D array dp[i][j] representing the length of the longest palindromic subsequence in s[i...j]. If s[i] == s[j], dp[i][j] = 2 + dp[i+1][j-1]. Otherwise, dp[i][j] = max(dp[i+1][j], dp[i][j-1]). We fill the table diagonally.

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

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

        return dp[0][n-1]