Problem Statement

The Longest Palindromic Subsequence problem involves finding the longest subsequence within a string that is also a palindrome. A subsequence is derived from another string by deleting some characters without changing the order of the remaining characters.

Approach Explanation

This problem can be solved using dynamic programming. The idea is to create a table where we can store the length of the longest palindromic subsequence for various substrings of the given string.

Dynamic Programming Structure:

1. Define a 2D DP table where dp[i][j] represents the length of the longest palindromic subsequence in the substring from index i to index j.
2. Initialize the diagonal of the table (where i == j) to 1, since any single character is a palindrome of length 1.
3. Fill the table for substrings of length 2 to the length of the string using the following logic:
   • If the characters at the two ends of the substring are the same, then dp[i][j] = dp[i + 1][j - 1] + 2.
   • If they are different, then dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]).
4. The final answer will be found in dp[0][n - 1], where n is the length of the string.

Time Complexity:

O(n^2), where n is the length of the string.

Space Complexity:

O(n^2) for the DP table.

Python Code

def longest_palindromic_subsequence(s):
    """
    Function to find the length of the longest palindromic subsequence in a string.

    Args:
    s (str): Input string.

    Returns:
    int: Length of the longest palindromic subsequence.
    """
    n = len(s)
    
    # Create a DP table initialized to 0
    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

    # Fill the DP table
    for length in range(2, n + 1):  # length of 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
input_string = "bbabcbcab"
length = longest_palindromic_subsequence(input_string)

print("Length of the longest palindromic subsequence is:", length)
    

Explanation of the Program

Let’s break down the structure of the program:

1. Input:

The input consists of a string for which we want to find the longest palindromic subsequence:

    input_string = "bbabcbcab"

2. DP Table Initialization:

A DP table is created with dimensions n x n, initialized to 0. This table is used to store the lengths of the longest palindromic subsequences for various substrings.

3. Base Case Setup:

The diagonal of the DP table is initialized to 1, indicating that each individual character is a palindrome of length 1.

4. Filling the DP Table:

The program iterates through all possible substring lengths, updating the DP table based on whether the characters at the two ends of the substring match or not.

5. Final Result:

The length of the longest palindromic subsequence can be found in dp[0][n - 1].

Example Execution:

For the provided input string, the output will display the length of the longest palindromic subsequence:

Length of the longest palindromic subsequence is: 7

This indicates that the longest palindromic subsequence in the string “bbabcbcab” has a length of 7.