Longest Palindromic Subsequence

Algorithms

The Longest Palindromic Subsequence (LPS) problem finds the length of the longest subsequence of a string that is also a palindrome.

Problem Statement

Given a string, find the length of the longest subsequence that reads the same forwards and backwards.

Dynamic Programming Solution

We use dynamic programming where $d p [i] [j]$ represents the length of the longest palindromic subsequence in the substring from index $i$ to $j$ .

Time Complexity

The time complexity is $O (n^{2})$ , where $n$ is the length of the string.

Implementation

def longest_palindromic_subsequence(s):
    """Dynamic Programming approach to find the longest palindromic subsequence."""
    n = len(s)
    
    # Create a table to store the lengths of longest palindromic subsequences
    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 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] and length == 2:
                dp[i][j] = 2
            elif 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 the longest palindromic subsequence: {}".format(longest_palindromic_subsequence(s)))  # Output: 7