Longest Palindromic Subsequence

MEDIUM

Description

Given a string s, find the longest palindromic subsequence's length 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".

Constraints:

1 <= s.length <= 1000
s consists only of lowercase English letters.

Approaches

Checkout 3 different approaches to solve Longest Palindromic Subsequence. Click on different approaches to view the approach and algorithm in detail.

Brute Force Recursion

This approach solves the problem by breaking it down into smaller, overlapping subproblems using recursion. We define a function that calculates the length of the longest palindromic subsequence for a given substring. The solution explores all possibilities without storing intermediate results, leading to exponential time complexity.

Algorithm

Define a recursive function solve(s, i, j) that computes the length of the longest palindromic subsequence in the substring s[i...j].
Base Cases:
- If i > j (empty substring), return 0.
- If i == j (single character), return 1.
Recursive Step:
- If s.charAt(i) == s.charAt(j), the characters at the ends match. They contribute 2 to the length. The rest of the palindrome is found in the inner substring. Return 2 + solve(s, i + 1, j - 1).
- If s.charAt(i) != s.charAt(j), the end characters don't match. We must discard one of them. We find the maximum length by either excluding the start character (solve(s, i + 1, j)) or the end character (solve(s, i, j - 1)). Return max(solve(s, i + 1, j), solve(s, i, j - 1)).
The initial call is solve(s, 0, s.length() - 1).

We define a recursive function, say solve(s, i, j), which computes the length of the longest palindromic subsequence in the substring s[i...j]. The logic is as follows:

Base Cases:
- If the start index i is greater than the end index j, it means we have an empty substring, so we return 0.
- If i equals j, we have a single-character substring, which is always a palindrome of length 1.
Recursive Step:
- If the characters at the ends of the substring, s[i] and s[j], are the same, they can form the ends of a palindrome. The length will be 2 plus the length of the LPS in the inner substring s[i+1...j-1]. So, we return 2 + solve(s, i + 1, j - 1).
- If the characters s[i] and s[j] are different, we cannot include both in the same palindrome. We have two choices:
  - Exclude s[i] and find the LPS in s[i+1...j].
  - Exclude s[j] and find the LPS in s[i...j-1]. We take the maximum of these two possibilities: max(solve(s, i + 1, j), solve(s, i, j - 1)).

The initial call to find the answer for the whole string s would be solve(s, 0, s.length() - 1). This method recomputes the same subproblems multiple times, making it highly inefficient.

class Solution {
    public int longestPalindromeSubseq(String s) {
        return solve(s, 0, s.length() - 1);
    }

    private int solve(String s, int i, int j) {
        // Base case 1: Empty substring
        if (i > j) {
            return 0;
        }
        // Base case 2: Single character substring
        if (i == j) {
            return 1;
        }

        // If characters at both ends match
        if (s.charAt(i) == s.charAt(j)) {
            return 2 + solve(s, i + 1, j - 1);
        } else {
            // If characters do not match
            return Math.max(solve(s, i + 1, j), solve(s, i, j - 1));
        }
    }
}

Complexity Analysis

Time Complexity: O(2^n), where n is the length of the string. For each position where characters don't match, the function branches into two subproblems, leading to an exponential number of calls.Space Complexity: O(n), where n is the length of the string. This space is used by the recursion stack. In the worst-case scenario, the recursion depth can go up to n.

Pros and Cons

Pros:

Simple to understand and implement.
Directly follows the problem's recursive definition.

Cons:

Extremely inefficient due to a large number of redundant computations for the same subproblems.
Will result in a 'Time Limit Exceeded' (TLE) error on most platforms for non-trivial input sizes.

Code Solutions

Checking out 3 solutions in different languages for Longest Palindromic Subsequence. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Longest Palindromic Subsequence

Patterns:

Dynamic Programming

Data Structures:

String

Companies:

Cisco |LinkedIn |Nutanix |