maximize-palindrome-length-from-subsequences

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

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

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

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

A subsequence 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.

A palindrome is a string that reads the same forward&nbsp;as well as backward.

&nbsp;
Example 1:

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

Example 2:

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

Example 3:

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

&nbsp;
Constraints:

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

longestPalindrome

Maximize Palindrome Length From Subsequences

Longest Palindromic Subsequence

longest-palindromic-subsequence

最长回文子序列

String

Dynamic Programming

给你两个字符串 <code>word1</code> 和 <code>word2</code> ，请你按下述方法构造一个字符串：

<ul>
	<li>从 <code>word1</code> 中选出某个 非空 子序列 <code>subsequence1</code> 。</li>
	<li>从 <code>word2</code> 中选出某个 非空 子序列 <code>subsequence2</code> 。</li>
	<li>连接两个子序列 <code>subsequence1 + subsequence2</code> ，得到字符串。</li>
</ul>

返回可按上述方法构造的最长 回文串 的 长度 。如果无法构造回文串，返回 <code>0</code> 。

字符串 <code>s</code> 的一个 子序列 是通过从 <code>s</code> 中删除一些（也可能不删除）字符而不更改其余字符的顺序生成的字符串。

回文串 是正着读和反着读结果一致的字符串。

 

示例 1：

<pre>输入：word1 = "cacb", word2 = "cbba"
输出：5
解释：从 word1 中选出 "ab" ，从 word2 中选出 "cba" ，得到回文串 "abcba" 。</pre>

示例 2：

<pre>输入：word1 = "ab", word2 = "ab"
输出：3
解释：从 word1 中选出 "ab" ，从 word2 中选出 "a" ，得到回文串 "aba" 。</pre>

示例 3：

<pre>输入：word1 = "aa", word2 = "bb"
输出：0
解释：无法按题面所述方法构造回文串，所以返回 0 。</pre>

 

提示：

<ul>
	<li><code>1 &lt;= word1.length, word2.length &lt;= 1000</code></li>
	<li><code>word1</code> 和 <code>word2</code> 由小写英文字母组成</li>
</ul>