[Dynamic Programming] Longest Palindromic Subsequence - Medium

Longest Palindromic Subsequence (LPS)

The Longest Palindromic Subsequence (LPS) problem is about finding the longest part of a string that reads the same way backward and forward. We can solve this problem using dynamic programming. We will use a 2D table to keep track of the results from smaller problems. This will help us find the length of the longest palindromic subsequence.

The main idea of LPS is to find characters that make a palindrome. We will skip characters that do not match. This method helps us reduce the search area.

In this article, we will talk about the Longest Palindromic Subsequence problem. We will explain what it is and why it is important in dynamic programming. We will go over different ways to solve this problem. This includes using dynamic programming in Java, Python, and C++. We will also discuss how to save space, use recursion with memoization, and use iterative methods. Finally, we will compare these different ways to solve the problem. Here are the topics we will cover:

  • Dynamic Programming Longest Palindromic Subsequence Solution
  • Understanding the Longest Palindromic Subsequence Problem
  • Dynamic Programming Approach for Longest Palindromic Subsequence in Java
  • Dynamic Programming Approach for Longest Palindromic Subsequence in Python
  • Dynamic Programming Approach for Longest Palindromic Subsequence in C++
  • Optimizing Space Complexity for Longest Palindromic Subsequence
  • Recursive Approach with Memoization for Longest Palindromic Subsequence
  • Iterative Approach for Longest Palindromic Subsequence
  • Comparing Different Approaches for Longest Palindromic Subsequence
  • Frequently Asked Questions

If you want to learn more about dynamic programming, you can check out these articles. They are about Dynamic Programming: Fibonacci Number and Dynamic Programming: Longest Common Subsequence.

Understanding the Longest Palindromic Subsequence Problem

The Longest Palindromic Subsequence (LPS) problem is about finding the longest subsequence in a string that is a palindrome. A palindrome is a word that reads the same from both sides. Examples are “racecar” and “level”. Our task is to find this subsequence in a quick way, especially when the string is long.

Problem Definition

We have a string s. Our job is to find out how long the longest subsequence is that can be a palindrome. The subsequence does not need to have characters next to each other. But it must keep the original order.

Example

  • Input: s = "bbabcbcab"
  • Output: 7
  • Explanation: The longest palindromic subsequence is “babcbab”.

Approach

  1. Dynamic Programming Table: We will use a 2D DP table. Here, dp[i][j] shows the length of the longest palindromic subsequence in the substring s[i...j].
  2. Base Case: If i == j, then dp[i][j] = 1. A single character is always a palindrome.
  3. Recurrence Relation:
    • If characters match: If s[i] == s[j], then we can say dp[i][j] = dp[i + 1][j - 1] + 2.
    • If they do not match: We take the bigger value, so dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]).

Complexity

  • Time Complexity: O(n^2). Here n is the length of the string.
  • Space Complexity: O(n^2) for the DP table.

This basic understanding of the Longest Palindromic Subsequence problem helps us to create solutions in different programming languages using dynamic programming methods.

Dynamic Programming Approach for Longest Palindromic Subsequence in Java

We can solve the Longest Palindromic Subsequence problem using dynamic programming in Java. We use a 2D array to save the lengths of palindromic subsequences. The idea is to create a solution by using values we already calculated.

Step-by-Step Approach:

  1. Initialization: We make a 2D array dp of size n x n. Here, n is the length of the input string. We set all dp[i][i] = 1 because a single character is a palindrome of length 1.

  2. Filling the DP Table:

    • We go through the length of subsequences from 2 to n.

    • For each length, we check the starting index i and find the ending index j = i + length - 1.

    • If the characters at i and j are the same, we do:

      dp[i][j] = dp[i + 1][j - 1] + 2

    • If they are different, we take the bigger of the two options:

      dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1])

  3. Result: The length of the longest palindromic subsequence is in dp[0][n - 1].

Java Code Implementation:

public class LongestPalindromicSubsequence {
    public static int longestPalindromicSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];

        // Every single character is a palindrome
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }

        // Build the table
        for (int length = 2; length <= n; length++) {
            for (int i = 0; i < n - length + 1; i++) {
                int j = i + length - 1;
                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];
    }

    public static void main(String[] args) {
        String s = "bbbab";
        System.out.println("Length of Longest Palindromic Subsequence: " + longestPalindromicSubseq(s));
    }
}

Explanation of the Code:

  • The method longestPalindromicSubseq finds the length of the longest palindromic subsequence in the string s.
  • The dynamic programming table dp keeps the lengths of palindromic subsequences for different parts of the string.
  • We print the result in the main method, showing how it works with an example input.

This approach has time complexity of O(n^2) and space complexity of O(n^2). If you want to read more about dynamic programming, you can check articles like Dynamic Programming - Coin Change.

Dynamic Programming Approach for Longest Palindromic Subsequence in Python

We can solve the Longest Palindromic Subsequence (LPS) problem using dynamic programming in Python. We will use a 2D array to keep track of the lengths of palindromic subsequences.

Algorithm Steps:

  1. Initialize a 2D array: We create a 2D array called dp with size n x n. Here, n is the length of the input string. Each dp[i][j] will show the length of the longest palindromic subsequence from index i to j.
  2. Base case: Every single character is a palindrome with length 1. So, we set dp[i][i] = 1 for all i.
  3. Build the table: We go through the substring lengths and fill the dp table:
    • If the characters at both ends of the substring are the same, we expand the palindrome: dp[i][j] = dp[i + 1][j - 1] + 2.
    • If they are different, we take the maximum by excluding either character: dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]).
  4. Result: The length of the longest palindromic subsequence for the whole string will be at dp[0][n - 1].

Python Code:

def longest_palindromic_subsequence(s: str) -> int:
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    
    # Base case: single character palindromes
    for i in range(n):
        dp[i][i] = 1
    
    # Fill the dp table
    for length in range(2, n + 1):  # Length of the substring
        for i in range(n - length + 1):
            j = i + length - 1
            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]

# Example usage
s = "bbabcbcab"
print("Length of Longest Palindromic Subsequence is:", longest_palindromic_subsequence(s))  # Output: 7

Complexity:

  • Time Complexity: O(n^2). Here, n is the length of the string.
  • Space Complexity: O(n^2) because of the 2D dp array.

We use this dynamic programming method to find the longest palindromic subsequence length in Python. This makes it good for medium-level problems in competitive programming and interviews. For more information about dynamic programming, you can check articles like Dynamic Programming - Longest Common Subsequence.

Dynamic Programming Approach for Longest Palindromic Subsequence in C++

We can solve the Longest Palindromic Subsequence (LPS) problem using dynamic programming. This problem is to find the longest subsequence in a string that reads the same from start to end and end to start.

C++ Implementation

Here is a simple C++ code to solve the LPS problem using dynamic programming:

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int longestPalindromicSubsequence(const string &s) {
    int n = s.length();
    vector<vector<int>> dp(n, vector<int>(n, 0));

    // Every single character is a palindrome of length 1
    for (int i = 0; i < n; i++) {
        dp[i][i] = 1;
    }

    // Build the DP table
    for (int length = 2; length <= n; length++) {
        for (int i = 0; i < n - length + 1; i++) {
            int j = i + length - 1;
            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]; // The length of the longest palindromic subsequence
}

int main() {
    string s = "bbabcbcab";
    cout << "Length of Longest Palindromic Subsequence: " 
         << longestPalindromicSubsequence(s) << endl;
    return 0;
}

Explanation of the Code

  • Initialization: We create a 2D vector dp to store lengths of palindromic subsequences. Each single character is set to 1 because it is a palindrome by itself.
  • Filling the DP Table: We go through all possible lengths of substrings. If the characters at both ends of the substring are the same, we update dp[i][j] to 2 + dp[i + 1][j - 1]. If they are not the same, we take the bigger value from the two possible substrings by removing either the first or the last character.
  • Result: The answer for the length of the longest palindromic subsequence is at dp[0][n-1], which covers the whole string.

This dynamic programming method runs in O(n^2) time and uses O(n^2) space. It is good for strings that are not too long. For better performance, we can look into ways to reduce space usage.

For more learning about dynamic programming methods, you can see the Dynamic Programming - Longest Common Subsequence article.

Optimizing Space Complexity for Longest Palindromic Subsequence

When we solve the Longest Palindromic Subsequence (LPS) problem using dynamic programming, we often make a 2D array. This array helps us store the lengths of palindromic subsequences. But this method can use a lot of space. The space complexity is O(n^2), where n is the length of the input string. To save space, we can use a better approach that cuts the space needed down to O(n).

Space Optimization Technique

We notice that to find the value of dp[i][j] (the length of the longest palindromic subsequence from index i to j), we only need values from the row before (dp[i+1][...]) and the current row (dp[i][...]). Because of this, we only need two arrays. We do not need a full matrix.

Implementation

Here is the optimized code in Python:

def longest_palindromic_subsequence(s: str) -> int:
    n = len(s)
    # Create two arrays to store results of the current and previous row
    prev = [0] * n
    curr = [0] * n

    for i in range(n - 1, -1, -1):
        curr[i] = 1  # Single character is a palindrome of length 1
        for j in range(i + 1, n):
            if s[i] == s[j]:
                curr[j] = 2 + prev[j - 1] if j > i + 1 else 2
            else:
                curr[j] = max(prev[j], curr[j - 1])
        prev = curr[:]  # Move to the next row

    return prev[n - 1]

# Example usage
s = "bbabcbab"
print("Length of Longest Palindromic Subsequence:", longest_palindromic_subsequence(s))

Explanation of the Code

  • We use two arrays prev and curr to keep the lengths of palindromic subsequences.
  • We go backward through the string. Each character can be a center of a palindromic subsequence.
  • For each pair of indices i and j, we check:
    • If the characters match (s[i] == s[j]), we update the current value based on the previous values.
    • If they do not match, we take the maximum value from previous calculations.
  • In the end, the length of the longest palindromic subsequence is in prev[n - 1].

Benefits of This Approach

  • Space Complexity: We cut it from O(n^2) to O(n).
  • Time Complexity: It stays O(n^2), because we still need to check each substring.

This better way is great for larger inputs where memory use matters. It helps us compute the Longest Palindromic Subsequence without needing a full 2D array. If we want to learn more about dynamic programming, we can check out related articles like Dynamic Programming: Longest Common Subsequence.

Recursive Approach with Memoization for Longest Palindromic Subsequence

We use the recursive approach to find the Longest Palindromic Subsequence. This approach breaks the problem into smaller parts. We want to find the longest palindromic subsequence by looking at characters from both ends of the string.

Recursive Relation

  1. If the characters at the two ends match (s[i] == s[j]), we get 2 + LPS(s, i+1, j-1).
  2. If they do not match, we use max(LPS(s, i+1, j), LPS(s, i, j-1)).

Base Case

  • If i > j, we return 0.
  • If i == j, we return 1 because a single character is a palindrome.

Memoization

To make the recursive approach faster, we can use memoization. This means we store the results of subproblems. This way, we do not have to calculate the same thing again. We can use a 2D array for this.

Implementation in Python

def longest_palindromic_subsequence(s: str) -> int:
    n = len(s)
    memo = [[-1 for _ in range(n)] for _ in range(n)]

    def lps(i: int, j: int) -> int:
        if i > j:
            return 0
        if i == j:
            return 1
        if memo[i][j] != -1:
            return memo[i][j]

        if s[i] == s[j]:
            memo[i][j] = 2 + lps(i + 1, j - 1)
        else:
            memo[i][j] = max(lps(i + 1, j), lps(i, j - 1))
        
        return memo[i][j]

    return lps(0, n - 1)

# Example usage
s = "bbbab"
print(longest_palindromic_subsequence(s))  # Output: 4

This code works well to find the length of the longest palindromic subsequence. The time it takes is O(n^2) and the space we use is also O(n^2) because of the memoization table. The recursive way helps us understand the problem better before we try harder dynamic programming solutions.

For more learning on dynamic programming, we can look at other problems like Dynamic Programming - Longest Common Subsequence or Dynamic Programming - Fibonacci Number with Memoization.

Iterative Approach for Longest Palindromic Subsequence

We can solve the Longest Palindromic Subsequence (LPS) problem with an iterative approach. This method uses dynamic programming to create a solution step by step. We build a 2D table. Each entry ( dp[i][j] ) shows the length of the longest palindromic subsequence in the substring from index ( i ) to index ( j ).

Algorithm Steps:

  1. Initialization:
    • We create a 2D array dp of size ( n n ) (where ( n ) is the length of the input string) and set it to 0.
    • Each character is a palindrome of length 1. So we set ( dp[i][i] = 1 ) for all ( i ).
  2. Filling the Table:
    • We look at substring lengths from 2 to ( n ):
      • For each starting index ( i ):
        • We calculate the ending index ( j = i + length - 1 ).
        • If the characters at ( i ) and ( j ) are the same, we update ( dp[i][j] ):
          • ( dp[i][j] = dp[i+1][j-1] + 2 )
        • If they are not the same, we take the maximum from the two possible palindromic subsequences:
          • ( dp[i][j] = (dp[i+1][j], dp[i][j-1]) )
  3. Result:
    • We find the length of the longest palindromic subsequence at ( dp[0][n-1] ).

Example Implementation in Java:

public class LongestPalindromicSubsequence {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];

        // Every single character is a palindrome of length 1
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }

        // Build the table in a bottom-up manner
        for (int length = 2; length <= n; length++) {
            for (int i = 0; i < n - length + 1; i++) {
                int j = i + length - 1;
                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];
    }
}

Example Implementation in Python:

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

        # Every single character is a palindrome of length 1
        for i in range(n):
            dp[i][i] = 1

        # Build the table in a bottom-up manner
        for length in range(2, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                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]

Example Implementation in C++:

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

        // Every single character is a palindrome of length 1
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }

        // Build the table in a bottom-up manner
        for (int length = 2; length <= n; length++) {
            for (int i = 0; i < n - length + 1; i++) {
                int j = i + length - 1;
                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];
    }
};

We use this iterative approach to find the longest palindromic subsequence in ( O(n^2) ) time and with ( O(n^2) ) space. For better space use, we can look at techniques that help reduce space in the next sections.

Comparing Different Approaches for Longest Palindromic Subsequence

When we solve the Longest Palindromic Subsequence (LPS) problem, we can use different methods. Each method has its good and bad sides. Here we look at three common ways: Dynamic Programming, Recursive with Memoization, and Iterative.

Dynamic Programming Approach

The Dynamic Programming (DP) method gives us a quick solution. It has a time complexity of O(n^2) and a space complexity of O(n^2). The main idea is to create a DP table. In this table, dp[i][j] shows the length of the longest palindromic subsequence in the substring from index i to j.

public int longestPalindromicSubseq(String s) {
    int n = s.length();
    int[][] dp = new int[n][n];

    for (int i = 0; i < n; i++) {
        dp[i][i] = 1; // Each character is a palindrome of length 1
    }

    for (int length = 2; length <= n; length++) {
        for (int i = 0; i < n - length + 1; i++) {
            int j = i + length - 1;
            if (s.charAt(i) == s.charAt(j)) {
                dp[i][j] = dp[i + 1][j - 1] + 2; // Characters match
            } else {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]); // Characters do not match
            }
        }
    }
    return dp[0][n - 1];
}

Recursive Approach with Memoization

We can also use recursion and improve it with memoization. This way, we do not calculate the same things again. The time complexity stays O(n^2), but the space complexity gets better to O(n) because of the memoization array.

def longestPalindromicSubseq(s: str) -> int:
    memo = {}

    def recurse(i, j):
        if i > j:
            return 0
        if i == j:
            return 1
        if (i, j) in memo:
            return memo[(i, j)]

        if s[i] == s[j]:
            memo[(i, j)] = 2 + recurse(i + 1, j - 1)
        else:
            memo[(i, j)] = max(recurse(i + 1, j), recurse(i, j - 1))

        return memo[(i, j)]

    return recurse(0, len(s) - 1)

Iterative Approach

We can also do an iterative approach. This way, we use just one array to keep the intermediate results. This helps to lower the space complexity to O(n).

int longestPalindromicSubseq(string s) {
    int n = s.size();
    vector<int> dp(n, 0);

    for (int i = n - 1; i >= 0; i--) {
        int prev = 0;
        for (int j = i; j < n; j++) {
            int temp = dp[j];
            if (i == j) {
                dp[j] = 1; // Single character
            } else if (s[i] == s[j]) {
                dp[j] = prev + 2; // Characters match
            } else {
                dp[j] = max(dp[j], dp[j - 1]); // Characters do not match
            }
            prev = temp;
        }
    }
    return dp[n - 1];
}

Summary of Approaches

  • Dynamic Programming: Best for big strings with O(n^2) time and O(n^2) space.
  • Recursive with Memoization: Easy to understand but still O(n^2) time and O(n) space.
  • Iterative: Good space use with O(n^2) time and O(n) space.

We choose the best way based on the problem needs. This includes string size and memory we have. For more about dynamic programming methods, we can check Dynamic Programming - Longest Common Subsequence.

Frequently Asked Questions

1. What is the Longest Palindromic Subsequence?

The Longest Palindromic Subsequence problem is about finding the longest subsequence in a string that is a palindrome. A palindrome is a sequence that looks the same backward and forward. For example, in the string “character”, the longest palindromic subsequence is “carac”. It has a length of 5. We need to understand this problem well to learn dynamic programming techniques.

2. How do I solve the Longest Palindromic Subsequence using Dynamic Programming?

To solve the Longest Palindromic Subsequence with dynamic programming, we can make a 2D array. This array stores the lengths of palindromic subsequences for different parts of the string. We fill this table by checking character matches and using values we calculated before. For more details and code examples, you can look at the Dynamic Programming Approach for Longest Palindromic Subsequence in Java.

3. What are the time and space complexities of the Longest Palindromic Subsequence algorithm?

The time complexity of the Longest Palindromic Subsequence algorithm with dynamic programming is O(n^2). Here n is the length of the string we give. The space complexity is also O(n^2). This is because we use a 2D table to save results. But if we use some optimization tricks, we can lower the space complexity to O(n) while keeping the same time complexity.

4. Can I use a recursive approach to solve the Longest Palindromic Subsequence problem?

Yes, we can use a recursive approach with memoization to solve the Longest Palindromic Subsequence problem. This means we check characters one by one and store the results of smaller problems. This way, we avoid counting the same thing again. This method has a time complexity of O(n^2) too. But some programmers find it easier to understand. For more details, check the section on Recursive Approach with Memoization for Longest Palindromic Subsequence.

5. How can I compare different approaches for solving the Longest Palindromic Subsequence?

To compare different ways of solving the Longest Palindromic Subsequence, we should look at time complexity, space complexity, and how easy it is to use. Dynamic programming gives a good balance of speed and efficiency. Meanwhile, recursive methods with memoization can be easier to understand. For more ideas on different methods, visit the section titled Comparing Different Approaches for Longest Palindromic Subsequence.