Solution For Longest Palindromic Subsequence
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]
Step by Step Implementation For Longest Palindromic Subsequence
public class Solution { public int longestPalindromeSubseq(String s) { int n = s.length(); int[][] dp = new int[n][n]; for (int i = n - 1; i >= 0; i--) { dp[i][i] = 1; for (int j = i + 1; j < n; j++) { if (s.charAt(i) == s.charAt(j)) { dp[i][j] = dp[i + 1][j - 1] + 2; } else { dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]); } } } return dp[0][n - 1]; } } /* The idea is to build a 2D dp array where dp[i][j] represents the length of the longest palindromic subsequence in the substring s[i..j]. We start by initializing the diagonal elements of the dp array to 1 because the longest palindromic subsequence of a string of length 1 is itself. Then, we fill in the rest of the dp array according to the following rules: If s[i] == s[j], then dp[i][j] = dp[i+1][j-1] + 2 If s[i] != s[j], then dp[i][j] = max(dp[i+1][j], dp[i][j-1]) The dp[0][n-1] element of the array will then contain the length of the longest palindromic subsequence in the entire string s. */
def longestPalindromeSubseq(s): # Base case: s is empty if not s: return 0 # Initialize a 2D array of size len(s) x len(s). # dp[i][j] will be the length of the longest palindromic subsequence # in s[i:j+1]. dp = [[0] * len(s) for _ in range(len(s))] # Consider each substring s[i:j+1]. In each iteration, we build # on the results from the previous iteration to calculate # dp[i][j]. for j in range(len(s)): # The longest palindromic subsequence of length 1 is just the # character at that index. dp[j][j] = 1 # Consider each character s[i] before s[j]. for i in reversed(range(j)): # If the characters at indices i and j match, then we can # extend the palindromic subsequence by 2. Otherwise, we # take the maximum of the two subsequences without s[i] # and without s[j]. 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]) # The length of the longest palindromic subsequence will be in # dp[0][len(s)-1]. return dp[0][len(s)-1]
var longestPalindromeSubseq = function(s) { // create a 2D array to store the results of our subproblems // each subproblem is the length of the longest palindromic subsequence // for the substring of s starting at index i and ending at index j const dp = Array(s.length).fill(null).map(() => Array(s.length).fill(0)); // base case: a palindromic subsequence of length 1 is just the character itself for (let i = 0; i < s.length; i++) { dp[i][i] = 1; } // iterate over the length of the string, starting with substrings of length 2 for (let len = 2; len <= s.length; len++) { // for each possible substring of length len, iterate over the start and end indices for (let i = 0; i <= s.length - len; i++) { const j = i + len - 1; // if the start and end characters are the same, we can extend the longest // palindromic subsequence by one character if (s[i] === s[j]) { dp[i][j] = dp[i+1][j-1] + 2; // if the start and end characters are not the same, we take the maximum // of the longest palindromic subsequences that don't include those characters } else { dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]); } } } // the result is the length of the longest palindromic subsequence for the entire string return dp[0][s.length - 1]; };
class Solution { public: int longestPalindromeSubseq(string s) { int n = s.size(); // Create a 2D array to store results of subproblems int dp[n][n]; // Strings of length 1 are palindrome of length 1 for (int i = 0; i < n; i++) dp[i][i] = 1; // Build the table in bottom up fashion for (int cl = 2; cl <= n; cl++) { for (int i = 0; i < n-cl+1; i++) { int j = i+cl-1; if (s[i] == s[j] && cl == 2) dp[i][j] = 2; else if (s[i] == s[j]) dp[i][j] = dp[i+1][j-1] + 2; else dp[i][j] = max(dp[i][j-1], dp[i+1][j]); } } return dp[0][n-1]; } };
using System; public class Solution { public int LongestPalindromeSubseq(string s) { // base case if (s.Length == 0) { return 0; } // create a 2D array to store the subproblem solutions int[,] dp = new int[s.Length, s.Length]; // fill in the array in a bottom-up fashion for (int i = s.Length - 1; i >= 0; i--) { for (int j = i; j < s.Length; j++) { // base case if (i == j) { dp[i, j] = 1; } // if the ith and jth characters are equal, then the // longest palindromic subsequence will be 2 + the // longest palindromic subsequence of the string // without those characters else if (s[i] == s[j]) { dp[i, j] = 2 + dp[i + 1, j - 1]; } // otherwise, the longest palindromic subsequence will // be the maximum of the two subproblems without the // ith or jth character else { dp[i, j] = Math.Max(dp[i + 1, j], dp[i, j - 1]); } } } // return the solution to the original problem return dp[0, s.Length - 1]; } }