最長偶数長パランドロームのプロセスシーケンス（中央2文字以外の異なる隣接文字付き）

Question

あなたは小文字の英語を含む文字列sを与えられます。次のパターンを満たすSの最大部分列の長さを見つける必要があります。 X1、X2、X3 ... XN、XN、... X3、X2、X1 ここで、XIはSのいくつかの文字です。唯一の制約は、Xnを除くxn、つまりxi！= x（i + 1）の除去はすべて、1 <= i

入力：文字列：s
出力：整数：2N
制約：1 <= | s | <= 10 ^ 3

サンプル入力1： "ACDBDEA"
サンプル出力1：4
説明：「ADDA」は、与えられたパターンに続く最長のプロセスです。

サンプル入力2： "abbacdeedc"
サンプル出力2：6
説明：「CDeedc」は、与えられたパターンに続く最長のプロセスです。

サンプル入力3： "TAKER"
サンプル出力3：0
説明：与えられたパターンに続きません。

---

この質問はコーディング面接で尋ねられ、それを解決する方法がわかりませんでした。最長のPalindromicのサブションを見つける方法を理解しましたが、隣接する異なる文字部分の実装方法がわかりません。助けてください。疑似コードは大丈夫です。

Answer 1

ゴールデンルール

これは動的プログラミングの黄金則です。

より小さなサブ問題を解決することができない場合は、情報が欠けているために、より大きなサブ問題を大きくすることができない場合は、その欠けている情報を与える追加パラメータをの追加して延長してください。

---

最初の試み

$ s は、 $ n $ 文字または $ s [0：n]。$

$ l [i] [j] [j] [j] [j] $ の長さは、 $ s [i ：j] $ 。基本ケースを把握するのは簡単です。 $ i $ 、および/または減少 $ j $ $ l [i] [j] $ の繰り返し関係。

偶数の条件を追加します。 $ e [i] [j] [j] [j] [j] [j] $ の長さは、 $ Sの長さの長さです。 ：j] $ 。 $ e [i] [j] [j] [j] $ の基本ケースと復帰関係を把握できます。 $ l [i] [j] $ 。

は、異なる隣接文字の条件を追加します。すなわち、中央の文字を除いて、手紙が2回表示されることはありません。 $ d [i] [j] $ の長さは、 $ s [i：j] $ 。注目されたとする可能性があるように、 $ d [i] [j] $ の再発は繰り返される可能性がありますので、繰り返し繰り返す可能性があります。文字。

ゴールデンルールは救助になるようになります。これまでに見つかった最長のサブシーケンスの最後に文字を分類する別のパラメータを追加します。そのため、そのサブシーケンスを正しく拡張する方法を決定できます。

$ d [i] [j] [\ lambda] $ の長さは、 $ s [i：j] $ は文字 $ \ lambda $ で終わります。つまり、 $ d [i] [j] [\ text {'} a \ text {'}] $ 、 $ d [i] [j] [\ text {'} b \ text {'}] $ 、 $ d [i] [j] [\ text {'} c \ text {'}] $ 、 $ \ cdots $ 、 $ d [i ] [j] [\ text {'} z \ text {'}] $ 。

• 最終回答は、 $ \ max_ \ lambda d [0] [n-1] [\ Lambda] $ と $ 0 $ 。

• $ s $の最初の a \ text {'} $ とします。 $ s [i] $ の $ s [\ vec {i _ {\ text { a \ text {'}}] $ 。 $ s $ の最初の \ text {'} $ を仮定します。 $ s [\ overleftarrow {j _ {\ text {'} a \ text {'}}] $ s [j] $ を後方に検索しました。 $ \ vec {i _ {\ text {'} \ text {'}}} \ または $ \ overleftarrow {j_ {\ text {'} \ text {'}}} $ は $ - 1 $ に設定されています。 > $ \ text {'} \ text {'} $ が見つかりません。 $ j \ ge i + 2 $ 、

  の場合

  $$ d [i] [j] [\ text {'} a \ text {'}]=begin {ケース} \ max（2,2 + \ max _ {\ mu \ not=text {'} a \ text {'}} d [\ vec {i _ {\ text {'} a \ text {'}}}} + 1] [\ overleftarrow {J _ {\ text {'} \ text {'}}] [\ mu]）＆\ text {if} 0 \ le \ vec {i _ {\ text {'} a \ text {'} \ \ overleftarrow {j _ {\ text {'} \ text {'}}}}}}} -1＆\ text {それ以外の場合は} \\ \ end {ケース} $$ $ \ mu $ は、すべて小文字の英語文字を介して実行されます。

• ベースケースは $$ d [i] [i] [\ text {'} a \ text {'}]= 0 $$

$ \ text {'} a \ text {'} $ variable $ \ lambda $ $ d [i] [j] [\ lambda] $ の復帰関係と基本ケースを書くことができます。

$ \ lambda $ パラメータに具現化されている追加情報では、再発関係を推測することは簡単です。

この試みが成功している間、私たちはより良いことができます。

---

2回目の試み

サブ問題を簡単にすることができます。

$ f [i] [j] $ $ sで始まる最長のそのような後処理の長さになります。 [i] $ と

PAN CLASS="math-container"> $ s [j] $ 。それから私たちは

を持っています

$$ f [i] [j]=begin {ケース} \ max（2,2 + \ max _ {\ mu \ not= s [i]} f [\ vec {i_ \ mu}] [\ overleftarrow {j_ \ mu}]）＆text {if} s [i]= s [j]、\\ -1＆\ text {それ以外の場合は} \\ \ end {ケース} $$ $ - 1 $ は "not found"を表します。小文字のすべての英語文字 $ \ mu $ 、 $ s [\ vec {i_ \ mu}] $ $ s [i] $ 、および $ \ mu $ です。 "math-container"> $ s [\ overleftarrow {j_ \ mu}] $ は、 $ \ mu $ です。 "Math-Container"> $ s [j] $ を後方検索しました。そのうちの1つが見つからない場合は、 $ f [\ vec {i_}] [\ overleftarrow {j_ \ mu}] $ は無視されます。

最終回答は、 $ \ max_ {i、j} f [i] [j] $ と0です。