<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>

// class Solution {
// public:
//     int longestPalindromeSubseq(string &s) {

//         vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
        
//         for (int i = s.size() - 1; i >= 0; i--) {

//             dp[i][i] = 1;

//             for (int j = i + 1; j < s.size(); j++) {

//                 int lengthIfMatch = 0, lengthIfSkipStart = 0, lengthIfSkipEnd = 0;
                
//                 if (s[i] == s[j]) {
//                     lengthIfMatch = 2 + dp[i + 1][j - 1];
//                 } 
//                 else {
//                     lengthIfSkipStart = dp[i + 1][j];
//                     lengthIfSkipEnd = dp[i][j - 1];
//                 }
//                 dp[i][j] = max({lengthIfMatch, lengthIfSkipStart, lengthIfSkipEnd});
//             }
//         }
//         return dp[0][s.size() - 1];
//     }
// };




class Solution {
public:
    int longestPalindromeSubseq(const string &s) {

        vector<int> curr(1001, 0);
        vector<int> next(1001, 0);
        
        for (int start = s.size() - 1; start >= 0; start--) {

            curr[start] = 1; // Single character is always a palindrome of length 1

            for (int end = start + 1; end < s.size(); end++) {
                
                int lengthIfMatch = 0, lengthIfSkipStart = 0, lengthIfSkipEnd = 0;
                
                // If characters at start and end indices are the same
                if (s[start] == s[end]) {
                    // Characters are the same
                    lengthIfMatch = 2 + next[end - 1];
                } 
                else { 
                    lengthIfSkipStart = next[end];

                    lengthIfSkipEnd = curr[end - 1];
                }
                curr[end] = max({lengthIfMatch, lengthIfSkipStart, lengthIfSkipEnd});
            }
            next = curr;
        }
        // The answer is stored in next[s.size() - 1], which covers the entire string
        return next[s.size() - 1];
    }
};

9000