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

} 

}