Longest Palindromic Subseqeunnce

94.Longest Palindromic Subsequence

String

Dynamic Programming

Problem Statement:

Given a string s, return the length of the longest palindromic subsequence 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.

Algorithm:

1. Use a 2D dynamic programming (DP) table where dp[i][j] represents the length of the longest palindromic subsequence in the substring s[i...j].
2. Initialize dp[j][j] to 1 for all indices j, as a single character is always a palindrome.
3. Iterate over all possible ending indices j and starting indices i:
• If the characters s[i] and s[j] are the same, then dp[i][j] = dp[i+1][j-1] + 2.
• Otherwise, dp[i][j] = max(dp[i+1][j], dp[i][j-1]).
4. Return dp[0][n-1], which represents the longest palindromic subsequence in the entire string.

Complexity:

Time: O(n²), where n is the length of the string | Space: O(n²) for the DP table.

Java Implementation:

public class Solution {
    public int longestPalindromeSubseq(String s) {
        int[][] dp = new int[s.length()][s.length()]; // DP table
        
        // Iterate over all ending indices j
        for (int j = 0; j < s.length(); j++) {
            dp[j][j] = 1; // A single character is a palindrome of length 1
            // Iterate over all starting indices i <= j
            for (int i = j - 1; i >= 0; i--) {
                // If the characters match
                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]);
            }
        }

        // The result is the length of the longest palindromic subsequence
        return dp[0][s.length() - 1];
    }
}

Python Implementation:

def longestPalindromeSubseq(s):
    n = len(s)
    dp = [[0] * n for _ in range(n)]  # DP table

    # Iterate over all ending indices j
    for j in range(n):
        dp[j][j] = 1  # A single character is a palindrome of length 1
        # Iterate over all starting indices i <= j
        for i in range(j - 1, -1, -1):
            if s[i] == s[j]:  # If the characters match
                dp[i][j] = dp[i + 1][j - 1] + 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])

    # The result is the length of the longest palindromic subsequence
    return dp[0][n - 1]

C++ Implementation:

#include 
#include 
using namespace std;

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size();
        vector> dp(n, vector(n, 0)); // DP table

        // Iterate over all ending indices j
        for (int j = 0; j < n; j++) {
            dp[j][j] = 1; // A single character is a palindrome of length 1
            // Iterate over all starting indices i <= j
            for (int i = j - 1; i >= 0; i--) {
                if (s[i] == s[j]) // If the characters match
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                else
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
            }
        }

        // The result is the length of the longest palindromic subsequence
        return dp[0][n - 1];
    }
};