Write a Python function to find the longest palindromic subsequence in a string.
LeoRobs
Posted by LeoRobs
Last Updated: August 20, 2024
Python Algorithm
Finding the Longest Palindromic Subsequence in a String
A palindromic subsequence is a sequence that reads the same backward as forward. The longest palindromic subsequence can be determined using dynamic programming. Below is a Python function that implements this approach.
Function Definition
def longest_palindromic_subsequence(s: str) -> int:
    n = len(s)
    # Create a 2D array to store 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

    # Build the dp array
    for length in range(2, n + 1):  # length of the subsequence
        for i in range(n - length + 1):
            j = i + length - 1  # Ending index of the current subsequence
            if s[i] == s[j]:  # Characters match
                dp[i][j] = dp[i + 1][j - 1] + 2
            else:  # Characters do not match
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])

    return dp[0][n - 1]  # The length of the longest palindromic subsequence
Explanation of the Function
1. Initialization: A 2D list dp is created to store the lengths of the longest palindromic subsequences. The dimensions are [n][n], where n is the length of the input string. 2. Base Case: Each character in the string is a palindrome of length 1. Therefore, the diagonal of the dp array is initialized to 1. 3. Dynamic Programming Approach: - The outer loop iterates over possible subsequence lengths from 2 to n. - The inner loop checks every possible start index i of the subsequence. The end index j is calculated based on the current length. - If the characters at indices i and j are the same, the value dp[i][j] is updated to be 2 + dp[i + 1][j - 1]. - If the characters differ, it takes the maximum value between the two cases: excluding the character at i or excluding the character at j. 4. Result: The function returns the value dp[0][n - 1], which represents the length of the longest palindromic subsequence in the entire string.
Usage Example
input_string = "bbabcbcab"
result = longest_palindromic_subsequence(input_string)
print(f"The length of the longest palindromic subsequence is: {result}")
Conclusion
This function efficiently computes the longest palindromic subsequence in a given string using a dynamic programming approach, maintaining a time complexity of O(n^2) and space complexity of O(n^2), making it suitable for strings of moderate length.
Default Image