# Longest Palindromic Subsequence
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/longest-palindromic-subsequence)
Canonical: https://scaleengineer.com/dsa/problems/longest-palindromic-subsequence
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** String
**Companies:** [Cisco](https://scaleengineer.com/companies/cisco), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Nutanix](https://scaleengineer.com/companies/nutanix)
---
## Problem
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
## 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.
**Time:** 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:** 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:** 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.
### Explanation
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:

1.  **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.

2.  **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.

```java
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));
        }
    }
}
```
### 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)`.

## Top-Down Dynamic Programming (Memoization)
This approach is an optimization of the brute-force recursion. It uses a 2D array (or a hash map) to store the results of subproblems that have already been solved. This technique, known as memoization, avoids redundant calculations and drastically improves the time complexity from exponential to polynomial.
**Time:** O(n^2). There are n*n possible unique subproblems defined by the pair `(i, j)`. Each subproblem is solved only once due to memoization. · **Space:** O(n^2), for the memoization table. The recursion stack also uses O(n) space, so the total space is dominated by the table.
**Pros:** Significantly more efficient than brute-force, with a polynomial time complexity.; Guaranteed to pass within time limits for the given constraints.; The code structure is still intuitive and closely follows the recursive definition.
**Cons:** Uses O(n^2) space, which might be substantial for very large n.; Recursive solutions can lead to stack overflow errors for very deep recursion, although this is unlikely given the problem constraints (n <= 1000).
### Explanation
The recursive structure remains the same as the brute-force approach. The key difference is the addition of a memoization table, `memo`, typically a 2D array initialized with a sentinel value (like `null` or -1) to indicate that a subproblem's result has not been computed yet.
The function `solve(s, i, j, memo)` works as follows:

1.  Before any computation, it checks if `memo[i][j]` already contains a valid result. If so, it returns the stored value immediately.
2.  If not, it computes the result using the same recursive logic as before.
3.  Before returning the computed result, it stores it in `memo[i][j]` for future use.

This ensures that each subproblem `(i, j)` is solved only once.

```java
class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        Integer[][] memo = new Integer[n][n];
        return solve(s, 0, n - 1, memo);
    }

    private int solve(String s, int i, int j, Integer[][] memo) {
        if (i > j) {
            return 0;
        }
        if (i == j) {
            return 1;
        }
        if (memo[i][j] != null) {
            return memo[i][j];
        }

        int result;
        if (s.charAt(i) == s.charAt(j)) {
            result = 2 + solve(s, i + 1, j - 1, memo);
        } else {
            result = Math.max(solve(s, i + 1, j, memo), solve(s, i, j - 1, memo));
        }
        
        memo[i][j] = result;
        return result;
    }
}
```
### Algorithm
- Create a 2D array `memo[n][n]` to store the results of subproblems, initialized with a sentinel value (e.g., `null` or `-1`).
- Define a recursive function `solve(s, i, j, memo)`.
- **Base Cases**: Same as the brute-force approach.
- **Memoization Check**: Before computing, check if `memo[i][j]` has already been computed. If so, return the stored value.
- **Recursive Step**: Same logic as the brute-force approach.
- **Store Result**: After computing the result for `(i, j)`, store it in `memo[i][j]` before returning.

## Bottom-Up Dynamic Programming with Space Optimization
This approach iteratively builds the solution from the smallest subproblems to the largest, eliminating recursion. It first solves for all substrings of length 1, then length 2, and so on, until it solves for the entire string. This bottom-up approach can be further optimized in terms of space from O(n^2) to O(n).
**Time:** O(n^2). We have two nested loops, each iterating up to `n` times, to fill the DP states. · **Space:** O(n). We use a single 1D array of size `n` to store the necessary DP states, making this the most memory-efficient approach.
**Pros:** Most efficient approach in terms of both time and space.; Iterative solution avoids recursion overhead and any risk of stack overflow.
**Cons:** The logic, especially with the single-array space optimization, can be less intuitive to understand compared to the more direct recursive or 2D DP solutions.
### Explanation
Instead of a top-down recursive approach, we can solve the problem iteratively, or bottom-up. We can use a 2D DP table, `dp[n][n]`, where `dp[i][j]` stores the length of the longest palindromic subsequence in `s[i...j]`. We would fill this table for substrings of increasing length.

The recurrence relation is the same:
- If `s[i] == s[j]`, `dp[i][j] = 2 + dp[i+1][j-1]`.
- If `s[i] != s[j]`, `dp[i][j] = max(dp[i+1][j], dp[i][j-1]`.

**Space Optimization**

Observing the recurrence, we see that to compute the `i`-th row of the DP table, we only need information from the `(i+1)`-th row. This allows us to optimize the space from O(n^2) to O(n) by using only one 1D array.

We iterate `i` from `n-1` down to `0`. A 1D array `dp` of size `n` will represent the current row being computed. At each step `j` in the inner loop, `dp[j]` still holds the value from the previous row (`i+1`), while `dp[j-1]` has already been updated for the current row `i`. A `prev` variable is used to keep track of the diagonal element `dp[i+1][j-1]`.

```java
class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[] dp = new int[n];
        
        for (int i = n - 1; i >= 0; i--) {
            dp[i] = 1; // Base case for substring of length 1
            int prev = 0; // Stores dp[i+1][j-1]
            
            for (int j = i + 1; j < n; j++) {
                int temp = dp[j]; // Store dp[i+1][j] before it's overwritten
                if (s.charAt(i) == s.charAt(j)) {
                    dp[j] = 2 + prev;
                } else {
                    dp[j] = Math.max(dp[j], dp[j-1]);
                }
                prev = temp;
            }
        }
        return dp[n - 1];
    }
}
```
### Algorithm
- Create a 1D array `dp` of size `n`.
- Iterate from the end of the string to the beginning with index `i` (from `n-1` down to `0`). This represents the starting character of the substring.
- For each `i`, set `dp[i] = 1` (a single character is a palindrome of length 1).
- Initialize a `prev` variable to 0. This will hold the value of `dp[i+1][j-1]` needed for the calculation.
- Start an inner loop for `j` from `i+1` to `n-1`. This represents the ending character of the substring.
- Inside the inner loop, save `dp[j]` (which currently holds `dp[i+1][j]`) into a `temp` variable.
- If `s.charAt(i) == s.charAt(j)`, update `dp[j] = 2 + prev`.
- Otherwise, update `dp[j] = max(dp[j], dp[j-1])`.
- After the update, set `prev = temp` to prepare for the next `j` iteration.
- After the loops complete, `dp[n-1]` will hold the result for the entire string `s[0...n-1]`.

# Solutions
### Java

```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 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 ]; } }
```

### CPP

```cpp
class Solution { public: int longestPalindromeSubseq ( string s ) { int n = s . size (); vector < vector < int >> dp ( n , vector < int > ( n , 0 )); 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 [ 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 ]; } };
```

### Python

```python
class Solution : def longestPalindromeSubseq ( self , s : str ) -> int : n = len ( s ) dp = [[ 0 ] * n for _ in range ( n )] for i in range ( n - 1 , - 1 , - 1 ): dp [ i ][ i ] = 1 # pre-set before inner loop for j in range ( i + 1 , n ): 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 ][ - 1 ] ########### class Solution : def longestPalindromeSubseq ( self , s : str ) -> int : n = len ( s ) dp = [[ 0 ] * n for _ in range ( n )] for i in range ( n ): dp [ i ][ i ] = 1 # cannot move it inside 'for j in range(1, n)' # because below 'for j in range' starting at 1 # so cannot put dp[j][j]=1 inside below for loop for j in range ( 1 , n ): for i in range ( j - 1 , - 1 , - 1 ): if s [ i ] == s [ j ]: dp [ i ][ j ] = dp [ i + 1 ][ j - 1 ] + 2 # "aa" => i=0,j=1 => dp[1][0] is 0, still works else : dp [ i ][ j ] = max ( dp [ i + 1 ][ j ], dp [ i ][ j - 1 ]) return dp [ 0 ][ - 1 ]
```