<p>You are given two strings, <code>word1</code> and <code>word2</code>. You want to construct a string in the following manner:</p>

<ul>
	<li>Choose some <strong>non-empty</strong> subsequence <code>subsequence1</code> from <code>word1</code>.</li>
	<li>Choose some <strong>non-empty</strong> subsequence <code>subsequence2</code> from <code>word2</code>.</li>
	<li>Concatenate the subsequences: <code>subsequence1 + subsequence2</code>, to make the string.</li>
</ul>

<p>Return <em>the <strong>length</strong> of the longest <strong>palindrome</strong> that can be constructed in the described manner. </em>If no palindromes can be constructed, return <code>0</code>.</p>

<p>A <strong>subsequence</strong> of a string <code>s</code> is a string that can be made by deleting some (possibly none) characters from <code>s</code> without changing the order of the remaining characters.</p>

<p>A <strong>palindrome</strong> is a string that reads the same forward&nbsp;as well as backward.</p>

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

<pre>
<strong>Input:</strong> word1 = &quot;cacb&quot;, word2 = &quot;cbba&quot;
<strong>Output:</strong> 5
<strong>Explanation:</strong> Choose &quot;ab&quot; from word1 and &quot;cba&quot; from word2 to make &quot;abcba&quot;, which is a palindrome.</pre>

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

<pre>
<strong>Input:</strong> word1 = &quot;ab&quot;, word2 = &quot;ab&quot;
<strong>Output:</strong> 3
<strong>Explanation:</strong> Choose &quot;ab&quot; from word1 and &quot;a&quot; from word2 to make &quot;aba&quot;, which is a palindrome.</pre>

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

<pre>
<strong>Input:</strong> word1 = &quot;aa&quot;, word2 = &quot;bb&quot;
<strong>Output:</strong> 0
<strong>Explanation:</strong> You cannot construct a palindrome from the described method, so return 0.</pre>

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

<ul>
	<li><code>1 &lt;= word1.length, word2.length &lt;= 1000</code></li>
	<li><code>word1</code> and <code>word2</code> consist of lowercase English letters.</li>
</ul>

class Solution:
    def longestPalindrome(self, word1: str, word2: str) -> int:
        # # choose a nonempty subseq of w1 and w2
        # # concatenate them
        # # return the length of the longest palindrome that can be formed

        # # brute force: top-down DFS

        # # current state is we're at index i in word1, index j in word 2, and if we've taken a char from both

        # M = len(word1)
        # N = len(word2)

        # @cache
        # def longest(i: int, j: int, both: bool) -> int:
        #     # current state: indices i,j in word1+word2
        #     # both indicates if we picked a character from both strings yet or not

        #     if i > j: return 0 # empty string
        #     if (i == M or j == M-1) and not both: return 0 # failed to pick >= 1 char from both strings

        #     ci = word1[i] if i < M else word2[i-M]
        #     cj = word1[j] if j < M else word2[j-M]

        #     if ci == cj:
        #         if i != j: return 2 + longest(i+1, j-1, both or (i < M and j >= M))
        #         else: return 1

        #     return max(longest(i+1, j, both), longest(i, j-1, both))

        # return longest(0, M+N-1, False)

        # # TC O(M+N squared), SC O(M+N squared)

        # # faster, albeit with complicated indexing: use DP
        # # and less memory: DP, plus noting that the best solution for (i,j) depends on (i+1,j[-1]) or (i[+1], j-1), i.e. prior two lengths
        # # at most, for O(M+N) memory


        ### NEW TECHNIQUE gleaned from fastest solution: "DP conditional max"
        # Normally the problem is a DP solution doesn't give us info about criteria, e.g. if we picked from both
        # so we can
        #   > have a cumulative max variable
        #   > if we get a dp[i][l] value that's better, update ans iff this new best solution involves picking from both strings
        # then return ans at the end

        M = len(word1)
        N = len(word2)

        # each length depends at most on prior two lengths
        best_lm2 = [0]*(M+N) # best length of length l-2 starting at each index i; empty string to start
        best_lm1 = [1]*(M+N) # ..................... l-1 ........................; single char is always a palindrome
        best = [0]*(M+N) # best at current length
        ans = 0 # max of all solutions where we picked a char from both; "conditional max trick"
        for l in range(2, M+N+1):
            # j == i + l - 1 <= M+N-1
            # i + l <= M+N
            # i <= M+N-l
            # i < M+N-l+1
            for i in range(M+N-l+1):
                j = i+l-1
                ci = word1[i] if i < M else word2[i-M]
                cj = word1[j] if j < M else word2[j-M]

                if ci == cj:
                    # ci  i+1 .. j-1  ci
                    # answer is 2 plus best over i+1..j-1, i.e. length l-2 starting at i+1
                    best[i] = 2 + best_lm2[i+1]
                    if i < M and j >= M: ans = max(ans, best[i])
                else:
                    # skip i or j
                    # if we skip i: best of i+1..j, best of length l-1 starting at i
                    # if we skip j: best of i..j-1, best of length l-1 starting at i+1
                    best[i] = max(best_lm1[i], best_lm1[i+1])

            # next iteration: curr len is next len-1, so best -> best_lm1
            best_lm1, best_lm2, best = best, best_lm1, best_lm2 # best is overwritten so we swap in best_lm2 intead of reallocating a new array

        return ans
1078