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: Input: s = "bbbab" Output: 4 Explanation: One possible longest palindromic subsequence is "bbbb".

Naive Approach (Brute Force)

A brute-force approach would involve generating all possible subsequences of the given string and checking each subsequence to see if it is a palindrome. We would then keep track of the longest palindromic subsequence found so far.

This approach is highly inefficient because the number of subsequences for a string of length n is 2^n. For each subsequence, checking if it's a palindrome takes O(n) time. Therefore, the overall time complexity would be O(n * 2^n).

Optimal Approach (Dynamic Programming)

A more efficient approach uses dynamic programming. We can define dp[i][j] as the length of the longest palindromic subsequence of the substring s[i...j]. Then we have the following recurrence relation:

1. If s[i] == s[j], then dp[i][j] = dp[i+1][j-1] + 2
2. If s[i] != s[j], then dp[i][j] = max(dp[i+1][j], dp[i][j-1])

Base case:

• dp[i][i] = 1 for all i

The length of the longest palindromic subsequence of the entire string s will be dp[0][n-1], where n is the length of s.

Edge Cases

• Empty string: If the input string is empty, the longest palindromic subsequence has length 0.
• Single character string: If the input string contains only one character, the longest palindromic subsequence has length 1.

Code (Java)

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

        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }

        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 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];
    }
}

Time and Space Complexity

• Time Complexity: O(n^2), where n is the length of the string s because we have two nested loops.
• Space Complexity: O(n^2) due to the dp table of size n x n.