# 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

###