Longest Palindromic Subsequence

Longest Palindromic Subsequence

Problem Description

Given a string s, the task is to find 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.

Example 1:

Input: s = "bbbab"
Output: 4
Explanation: One possible longest palindromic subsequence is "bbbb".

Example 2:

Input: s = "cbbd"
Output: 2
Explanation: One possible longest palindromic subsequence is "bb".

Naive Approach (Recursion)

A naive approach is to use recursion. For a given string s, if the first and last characters are the same, then the longest palindromic subsequence will be 2 plus the longest palindromic subsequence of the substring excluding the first and last characters. If the first and last characters are different, then the longest palindromic subsequence will be the maximum of the longest palindromic subsequence of the string excluding the first character and the longest palindromic subsequence of the string excluding the last character.

Code (Python):

def longest_palindromic_subsequence_recursive(s):
    if not s:
        return 0
    if len(s) == 1:
        return 1

    if s[0] == s[-1]:
        return 2 + longest_palindromic_subsequence_recursive(s[1:-1])
    else:
        return max(longest_palindromic_subsequence_recursive(s[1:]), longest_palindromic_subsequence_recursive(s[:-1]))

Time Complexity: O(2^n), where n is the length of the string. Space Complexity: O(n) due to the recursion depth.

This naive recursive solution has overlapping subproblems and thus is not optimal.

Optimal Approach (Dynamic Programming)

An optimal approach is to use dynamic programming to store the results of subproblems and avoid recomputation. We can create a 2D array dp where dp[i][j] stores the length of the longest palindromic subsequence of the substring s[i:j+1].

Algorithm:

1. Initialize a 2D array dp of size n x n with 0s.
2. For substrings of length 1, dp[i][i] = 1.
3. Iterate over substrings of increasing length:
   • For each substring s[i:j+1]:
     • If s[i] == s[j], then dp[i][j] = dp[i+1][j-1] + 2.
     • Else, dp[i][j] = max(dp[i+1][j], dp[i][j-1]).
4. The result is dp[0][n-1].

Code (Python):

def longest_palindromic_subsequence_dp(s):
    n = len(s)
    dp = [[0] * n for _ in range(n)]

    for i in range(n):
        dp[i][i] = 1

    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]

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

Edge Cases

• Empty string: Return 0.
• Single-character string: Return 1.
• String with all the same characters: Return the length of the string.

Summary

The optimal solution utilizes dynamic programming to find the length of the longest palindromic subsequence in O(n^2) time and O(n^2) space. This avoids the exponential time complexity of the naive recursive approach by storing and reusing the results of subproblems.