最长的偶数回文后子序列（除了中心2字母外，具有不同的相邻字符）

Question

给出一个包含小写英语字符的字符串。您需要找到满足以下模式的最大子序列的长度： x1，x2，x3 ... xn，xn，... x3，x2，x1 其中xi是s的一些特征。唯一的约束是除xn外，唯一的字符应该是相同的，即xi！= x（i + 1）所有1 <= i < ñ。

输入：字符串：s
输出：整数：2n
约束：1 <= | S | <= 10 ^ 3

样本输入1：“ACDBDEA”
样品输出1：4
说明：“adda”是给定模式后的最长的子序列。

样本输入2：“abbacdeedc”
样品输出2：6
说明：“CDEDC”是给定模式后的最长的子序列。

样本输入3：“taker”
样品输出3：0
说明：无后续跟随给定的模式。

---

这个问题被问到了一个编码面试中，我不知道如何解决它。我明白如何找到最长的回文后续，但不知道如何实现不同的相邻字符部分。请帮忙。伪代码很好。

Answer 1

golden规则

这是动态编程的黄金规则。

当由于缺少信息而不能将较小子问题的解决方案组合成更大的子问题，通过添加参数扩展子问题，这给出了缺失信息。

---

首次尝试

$ s $ 是一个 $ n $ 字母， $ S [0：n]。$

let $ l [i] [j] $ 是 $ s [i的最长回文后子变量的长度：j] $ 。很容易弄清楚基本情况，并且通过增加<跨度类=“math-container”> $ i $ 和/或减少 $ j $ ，<跨度类=“math-container”> $ l [i]的复发关系[j] $ 。

现在添加均匀长度的条件。让 $ e [i] [j] $ 是 $ s [i的最长偶数的偶数 - 长度的长度的长度：j] $ 。我们可以弄清楚 $ e [i] [j] $ 的复发关系，类似于 $ l [i] [j] $ 。

现在添加不同相邻字母的条件，即，除了中心的字母之外，没有任何字母可以出现两次。让 $ d [i] [j] $ 是 $ s [i：j] $ 。如您所要所述，我们无法弄清楚<跨度类=“math-container”> $ d [i] [j] $ 的复发关系，因为延伸到更长的子项可能会重复介绍字母。

黄金法则来救援。添加另一个参数，该参数在到目前为止发现的最长后续的末尾的字母上，以便我们可以确定如何正确扩展其后续的。

let $ d [i] [j] [\ lambda] $ 是 $ s [i：j] $ 以字母 $ \ lambda $ 。也就是说，我们将计算 $ d [i] [j] [\ text {'} a \ text {'}] $ ， $ d [i] [j] [\ text {'} b \ text {'}] $ ， $ d [i] [j] [\文本{'} c \ text {'}] $ ， $ \ cdots $ ， $ d [i ] [j] [\ text {'} z \ text {'}] $ 。

• 最终答案是 $ \ max_ \ lambda d [0] [n-1] [\ lambda] $ 和 $ 0 $ 。

• 假设第一个 $ \ text {'} a \ text {'} $ 在 $ s $ $ s [i] $ 出现在 $ s [\ vec {i _ {\ text { '} a \ text {'}}}] $ 。假设第一个 $ \ text {'} a \ text {'} $ 中 $ s $ 出现在 $ s [\ overleftarrow {j _ {\ text {} a \ text {'}}] $ $ s [j] $ 向后搜索。 $ \ vec {i _ {\ text {'} a \ text {'}} $ 或 $ \ overleftrarrow {j_ {\ text {'} a \ text {'}} $ 设置为 $ - 1 $ 如果 $ \ text {'} a \ text {'} $ 分别找不到。我们有，对于 $ j \ ge i + 2 $ ，

  $$ d [i] [j] [\ text {'} a \ text {'}]=begin {iscus} \ max（2,2 + \ max _ {\ mu \ not=text {'} a \ text {'}} d [\ vec {i _ {\ text {'} a \ text {'}} + 1] [overleftarrow {j _ {\ text {'} a \ text {'}}}] [\ mu]）＆\ text {if} 0 \ le \ vec {i _ {\ text {'} a \ text {'} }} \ lt \ overleftrarrow {j _ {\ text {'} a \ text {'}}}，\\ -1＆\ text {否则，}} \\ \结束{案例} $$ 其中 $ \ mu $ 通过所有小写的英文字母运行。

• 基本情况是 $$ d [i] [i] [\ text {'} a \ text {'}]= 0。$$

概括 $ \ text {'} a \ text {'} $ 变量 $ \ lambda $ ，我们可以编写 $ d [i] [j] [\ lambda] $

的重复关系和基本情况。

请注意，在 $ \ lambda $ 参数中，使用

虽然这种尝试成功，我们可以做得更好。

---

第二次尝试

我们可以简化子问题。

let $ f [i] [j] $ 是在 $ s中开始的最长诸如此的子序列的长度[i] $ 并以

PAN类=“MATH-CATER容器”> $ S [J] $ 。然后我们有

$$ f [i] [j]=begin {iss} \ max（2,2 + \ max _ {\ mu \ not= s [i]} f [\ vec {i_ \ mu}] [\ overleftrarrow {j_ \ mu}]）＆\ text {if} s [i]= s [j]，\\ -1＆\ text {否则，}} \\ \结束{案例} $$ 其中 $ - 1 $ 代表“找不到”。对于所有小写英文字母 $ \ mu $ ， $ s [\ vec {i_ \ mu}] $ 是 $ s [i] $ 之后出现的第一个 $ \ mu $ 。 “数学集装箱”> $ s [overleftarrow {j_ \ mu}] $ 是第一个 $ \ mu $ $ s [j] $ 向后搜索。如果其中一个找不到，术语 $ f [\ vec {i_ \ mu}] [\ overleftrarrow {j_ \ mu}] $ 被忽略。

最终答案是 $ \ max_ {i，j} f [i] [j] $ 和0。