<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:
    def longestPalindromeSubseq(self, s: str) -> int:
        
        str_len = len(s)
        
        if str_len == 1:
            return 1
        
        if str_len == 2:
            return 2 if s[0] == s[1] else 1
        
        n_minus2_dict: Dict[Tuple[int, int], int] = {}
        n_minus1_dict: Dict[Tuple[int, int], int] = {}
        cur_len_dict: Dict[Tuple[int, int], int] = {}
        
        # populate for length 1 and 2 as base case
        
        for i in range(str_len):
            n_minus2_dict[(i, i)] = 1
        
        for i in range(str_len - 1):
            n_minus1_dict[(i, i + 1)] = (
                2 if s[i] == s[i + 1] else 1
            )
        
        # 2 means extra 2 characters i.e. str len == 3
        for extra_str_len in range(2, str_len):
            
            for i in range(str_len - extra_str_len):
                lower = i
                upper = i + extra_str_len
                
                if s[lower] == s[upper]:
                    # we can add length 2 here to the prev one's max longest
                    cur_len_dict[(lower, upper)] = n_minus2_dict[(lower + 1, upper - 1)] + 2
                else:
                    # it's a max between ignoring 1st char vs last char
                    cur_len_dict[(lower, upper)] = max(
                        n_minus1_dict[(lower + 1, upper)],
                        n_minus1_dict[(lower, upper - 1)],
                    )
                
            # move the dicts "back"wards
            n_minus2_dict = n_minus1_dict
            n_minus1_dict = cur_len_dict
        
        return cur_len_dict[(0, str_len - 1)]
117731