Longest Palindromic Subsequence - Leetcode Solution

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

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

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

Input: "cbbd" Output: 2 Explanation: One possible longest palindromic subsequence is "bb".

Solution: This problem can be solved using dynamic programming. Let dp[i][j] represent the length of longest palindromic subsequence between indices i and j (inclusive). The base case is when i == j, in which the length of the palindromic subsequence is 1. Then, we can fill up the dp array using the following recurrence relation:

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])

The first case handles when the first and last characters are the same, in which case we add 2 to the length of the longest palindromic subsequence between indices i+1 and j-1. The second case handles when the first and last characters are different, in which case we take the maximum between the length of longest palindromic subsequence between indices i+1 and j, and the length of longest palindromic subsequence between indices i and j-1.

Finally, the answer is in dp[0][n-1], where n is the length of the string s.

Here's the Python code:

def longestPalindromeSubseq(s: str) -> int: n = len(s) dp = [[0]*n for _ in range(n)] for i in range(n): dp[i][i] = 1 for i in range(n-1, -1, -1): for j in range(i+1, n): 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]) return dp[0][n-1]

1