最長回文部分列と部分文字列
区間DPで最長回文部分列を求め、中心から展開する方法で最長回文部分文字列を求めます。
「最長回文部分列と部分文字列」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
回文の定義を再確認
回文部分列とは、前から読んでも後ろから読んでも同じになる部分列（要素が連続している必要はありません）です。回文部分文字列では、文字が連続している必要があります。'bbbab' の場合、最長回文部分列は 'bbbb'（長さ4）であり、最長回文部分文字列は 'bbb'（長さ3）です。名前は似ていますが、この2つの問題には異なる手法が必要です。
最長回文部分列: LPS の状態
dp[i][j] を、s[i..j] に含まれる最長回文部分列の長さと定義します。漸化式は次のとおりです。s[i] == s[j] の場合、dp[i][j] = dp[i+1][j-1] + 2 です。一致する2つの文字によって、内側の回文を両端から拡張できるためです。それ以外の場合は、dp[i][j] = max(dp[i+1][j], dp[i][j-1]) です。左端または右端の文字を飛ばします。ベースケースは、すべての1文字について dp[i][i] = 1 です。
s = 'bbbab'
n = len(s)
dp = [[0]*n for _ in range(n)]
for i in range(n):
dp[i][i] = 1
print('Base cases set, dp[i][i] = 1 for all i')LPS の埋める順序と実装
一般的な区間 DP と同じパターンで、LPS の表を区間の長さが増える順序に埋めます。長さ2以上の各区間 [i, j] について、両端の文字が一致するかを確認し、漸化式を適用します。最終的な答えは、文字列全体の LPS である dp[0][n-1] です。
def longest_palindromic_subsequence(s):
n = len(s)
dp = [[0]*n for _ in range(n)]
for i in range(n):
dp[i][i] = 1
for length in range(2, n+1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j]:
inner = dp[i+1][j-1] if length > 2 else 0
dp[i][j] = inner + 2
else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
return dp[0][n-1]
print(longest_palindromic_subsequence('bbbab')) # 4LCS と同値な LPS
洗練された別解として、文字列 s の LPS は、s と反転した文字列 s[::-1] の LCS に等しくなります。これは、s の回文部分列が、s とその反転文字列の共通部分列になるためです。この変換により、LCS のコードをそのまま再利用できます。'bbbab' を反転すると 'babbb' になり、両者の LCS は4です。
def lps_via_lcs(s):
t = s[::-1]
m, n = len(s), len(t)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if s[i-1] == t[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
print(lps_via_lcs('bbbab')) # 4最長回文部分文字列: ブルートフォース
最長回文部分文字列では、文字が連続している必要があります。ブルートフォースでは O(n²) 個の部分文字列をすべて調べ、それぞれを O(n) 時間で検証するため、合計で O(n³) かかります。より高速な方法として、O(n²) の時間計算量と空間計算量で解く区間 DPと、O(n²) の時間計算量かつ O(1) の空間計算量で解く中心展開の2つがあります。面接では、中心展開の方が定数倍が小さくコードも簡潔なため、こちらが好まれます。
回文部分文字列に対する区間 DP
dp[i][j] = True を、s[i..j] が回文である場合に設定します。漸化式は dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1] です。ベースケースは、dp[i][i] = True と dp[i][i+1] = (s[i] == s[i+1]) です。見つかった回文の最大長を記録します。長さが増える順序で表を埋めます。時間計算量は O(n²)、空間計算量も O(n²) です。
def longest_palindrome_dp(s):
n = len(s)
dp = [[False]*n for _ in range(n)]
start, max_len = 0, 1
for i in range(n):
dp[i][i] = True
for i in range(n-1):
if s[i] == s[i+1]:
dp[i][i+1] = True
start, max_len = i, 2
for length in range(3, n+1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j] and dp[i+1][j-1]:
dp[i][j] = True
if length > max_len:
start, max_len = i, length
return s[start:start+max_len]
print(longest_palindrome_dp('babad')) # 'bab' or 'aba'中心展開法
中心展開では、各文字（および隣接する各文字ペア）を回文の中心候補として試し、左右の文字が一致する限り外側へ展開します。中心の候補は 2n-1 個あります（奇数長のものが n 個、偶数長のものが n-1 個です）。各展開には最大 O(n) 時間かかるため、全体では O(n²) 時間、O(1) 空間となり、ほとんどの面接で最適な方法です。
def longest_palindrome_expand(s):
def expand(l, r):
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1
r += 1
return r - l - 1 # length of palindrome
start, max_len = 0, 1
for i in range(len(s)):
odd = expand(i, i) # odd-length
even = expand(i, i+1) # even-length
best = max(odd, even)
if best > max_len:
max_len = best
start = i - (best - 1) // 2
return s[start:start+max_len]
print(longest_palindrome_expand('cbbd')) # 'bb'LPS の空間最適化
LPS の区間 DP では O(n²) の空間を使います。実際の部分列ではなく長さだけが必要な場合は、dp[i][j] が dp[i+1][j-1]、dp[i+1][j]、dp[i][j-1] にしか依存しないことを利用できます。行を再利用し、対角要素を1つ保存することで、空間を O(n) に削減できます。ただし実装は複雑になり、面接で必要になることはほとんどありません。
LPS の復元
実際の回文部分列を復元するには、DP 表をさかのぼります。(0, n-1) から始めます。s[i] == s[j] の場合は、その文字を結果の両端に追加して (i+1, j-1) に移動します。それ以外の場合は、(i+1, j) と (i, j-1) のうち値が大きい方へ移動します。この貪欲なバックトレースによって、最適な回文部分列を1つ復元できます。
def reconstruct_lps(s, dp):
result = []
i, j = 0, len(s) - 1
while i < j:
if s[i] == s[j]:
result.append(s[i])
i += 1; j -= 1
elif dp[i+1][j] > dp[i][j-1]:
i += 1
else:
j -= 1
# middle character for odd-length
mid = [s[i]] if i == j else []
return ''.join(result + mid + result[::-1])
print('Traceback recovers one optimal LPS')LPS と LCS の時間計算量の比較
区間 DP による LPS と LCS は、どちらも時間計算量が O(n²)、空間計算量も O(n²)です。最長回文部分文字列に対する中心展開は、時間計算量が O(n²) ですが、空間計算量は O(1) です。Manacher のアルゴリズムを使えば、部分文字列の問題を O(n) の時間計算量と空間計算量で解けますが、十分に複雑なため、面接官が期待することはほとんどありません。ほとんどの面接では、部分文字列版に対する最適解として中心展開が期待されます。
よくある落とし穴とエッジケース
次の点に注意してください。(1) 部分列と部分文字列を混同する — これらは異なる問題であり、解法も異なります。(2) 長さ2の区間に対する区間DPのベースケースには特別な処理が必要です。これは dp[i+1][j-1] が dp[i+1][i]（空の区間）になるためです。(3) 中心からの展開では、max_len = 1 で初期化してください（1文字だけでもすべて回文です）。(4) 結果を取り出すときは、中心から正しい開始インデックスを求めるために start = i - (best-1)//2 を計算してください。
クイックチェック
このレッスンで学んだ Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認しましょう。
レッスンのまとめ
このレッスンでは、LPSでは区間DPを使い、文字が一致する場合の漸化式が dp[i][j] = dp[i+1][j-1]+2 になること、最長回文部分文字列は O(n²) 時間・O(1) 空間の中心からの展開で解くのが最適であること、そしてLPSは文字列とその反転文字列のLCSに等しいことを学びました。次は、回文テーブルと最小カットを求める1D DPを組み合わせる回文分割 IIに取り組みます。
よくある質問
「最長回文部分列と部分文字列」レッスンは無料ですか？
はい。「最長回文部分列と部分文字列」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「最長回文部分列と部分文字列」で何を学びますか？
区間DPで最長回文部分列を求め、中心から展開する方法で最長回文部分文字列を求めます。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。
「最長回文部分列と部分文字列」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。