<p>Given a string <code>s</code>, find <em>the longest palindromic <strong>subsequence</strong>&#39;s length in</em> <code>s</code>.</p>

<p>A <strong>subsequence</strong> is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

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

<p><strong class="example">Example 2:</strong></p>

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

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 1000</code></li>
	<li><code>s</code> consists only of lowercase English letters.</li>
</ul>

#include<string>
#include<algorithm>
class Solution {
        int longestCommonSubsequence(string text1, string text2) {
        int length1 = text1.size(), length2 = text2.size();
        // vector<vector<int>> dp(length1+1, vector<int>(length2+1, -1));

        vector<int> prev(length2+1), curr(length2+1);

        // Base case
        for(int i=0;i<length1 + 1; i++){
            prev[0] = 0;
        }
        string s = "";

        // Main code
        for(int i=1; i<length1+1; i++){
            for(int j =1; j<length2+1;j++){
                if(text1[i-1] == text2[j-1]){
                    curr[j] = 1 + prev[j-1];

                    //printing string
                    s+=text1[i-1];

                }
                else{
                   curr[j] = max(prev[j],curr[j-1]);
                }
            }
                prev = curr;
        }
        // cout<<s<<endl;
        return prev[length2];
    }
public:
    int longestPalindromeSubseq(string s) {
        string s2 =s;
        reverse(s2.begin(),s2.end());
        return  longestCommonSubsequence(s, s2);
    }
};

36800