# 516. Longest Palindromic Subsequence

## Problem Statement

<br>

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.

&#x20;

**Example 1:**

<pre><code><strong>Input: s = "bbbab"
</strong><strong>Output: 4
</strong><strong>Explanation: One possible longest palindromic subsequence is "bbbb".
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: s = "cbbd"
</strong><strong>Output: 2
</strong><strong>Explanation: One possible longest palindromic subsequence is "bb".
</strong></code></pre>

&#x20;

**Constraints:**

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

## Intuition

```
Appraoahc:

We reverse the string and find the LCS, Intuition
When we reverse the string, The palindromes will remain same

in reverse as well as og
but all other changes

eg-> abad
     daba
We can find aba
```

### Links

<https://leetcode.com/problems/longest-palindromic-subsequence/>

### Video Links

### Approach 1:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    int lcs(string &s1, string &s2, int i, int j, vector<vector<int>> &dp){
        if( i<0 or j<0)
            return 0;

        if(dp[i][j] != -1)
            return dp[i][j];

        if(s1[i] == s2[j])
            return dp[i][j] = 1 + lcs(s1, s2, i-1, j-1, dp);

        return dp[i][j] = max( lcs(s1, s2, i-1, j, dp), lcs(s1, s2, i, j-1, dp) );
    }

    int longestPalindromeSubseq(string s) {
        string s2 = s; 
        reverse(s2.begin(), s2.end());
        int i = s.size()-1;
        vector<vector<int>> dp(i+1, vector<int>(i+1, -1));

        return lcs(s, s2, i, i, dp);
    }
};

```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://coding-9.gitbook.io/untitled/dynamic-programming/dp-on-strings/516.-longest-palindromic-subsequence.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.