Longest Palindromic Substring
小文字の英字からなる文字列 s が与えられます。その最長の回文部分文字列、つまり前から読んでも後ろから読んでも同じになる、連続した文字の最長の並びを返してください。最長の長さを持つ部分文字列が複数ある場合は、最も左から始まるものを返してください。
関数
- sstring
- 検索する小文字の文字列
- 戻り値string
- s の最長回文部分文字列。同じ長さのものが複数ある場合は、最も左にあるもの
制約
1 ≤ s.length ≤ 2000sには小文字の英字のみが含まれています。- 最長の長さを持つ回文が複数ある場合、答えは開始インデックスが最小のものです。
例
- 入力
- s = "bananas"
- 出力
- "anana"
- 説明
"anana"は両端から読んでも同じで、5文字です。これより長い部分はありません。"banana"はbで始まりaで終わり、"ananas"はaで始まりsで終わります。また、単語全体はbで始まりsで終わります。
- 入力
- s = "xyzzyabba"
- 出力
- "yzzy"
- 説明
"yzzy"と"abba"はどちらも長さ 4 の回文で、それより長いものはありません。"yzzy"はインデックス 1 から始まり、インデックス 5 から始まる"abba"より前にあるため、同点の場合はこれが選ばれます。
- 入力
- s = "abcd"
- 出力
- "a"
- 説明
- 同じ文字は2つないため、すべての回文は1文字です。最も左にあるのは
"a"です。
提出時に隠しテスト+18件
発展問題
O(n) 時間で答えを見つけられますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
すべての回文は中央を軸に対称です。
"aba"と"abba"を見てください。それぞれの中央はどこにありますか。また、長さ n の文字列には、中央がいくつ考えられますか？中央に立ちます。その両側の文字が一致すれば、前より2文字長い回文になります。いつ拡張を止めるべきでしょうか。また、なぜそれ以上長い回文は同じ中央を共有できないのでしょうか。
2n-1個の中心（各文字と隣り合う2文字の間のすき間）について、文字が一致する間は外側へ広げ、最長の結果を記録します。新しい回文がそれより厳密に長い場合にのみ最良の結果を更新することで、同じ長さなら最も左にあるものが選ばれます。
解説
回文は中央を軸に対称で、その中央は1文字（奇数の長さ、たとえば"anana"）か、同じ2文字の間の隙間（偶数の長さ、たとえば"abba"）のどちらかです。すべての部分文字列を個別に調べる方法では、この構造が活かされず、計算量は O(n³) になります。中央から外側へ回文を伸ばしていけば、各比較を再利用できるため、追加メモリ O(1) で探索時間を O(n²) に抑えられます。
すべての部分文字列を確認する
正しいが、最大のテストでは終わらない
考え方
部分文字列は、最初のインデックス i と最後のインデックス j で定まります。2つのポインタを使って判定します。s[i] と s[j] を比較し、次に s[i+1] と s[j-1] を比較する、というように、最初に不一致が見つかるまで続けます。不一致がないままポインタが出会うか交差したら、その部分文字列は回文です。見つけた中で最長のものを保持します。
同率時のルールとして、開始位置を左から右へ調べ、新しい回文が厳密に長い場合にのみ、最良のものを置き換えます。後に見つかった同じ長さの回文が先に見つかったものを押しのけることはないため、最も左にあるものが返されます。
この方法では n(n+1)/2 個すべての部分文字列を調べるため、答えを見逃すことはありません。各判定で部分文字列の半分近くを調べることがあるため、処理は遅くなります。a が2000個並んだ文字列の場合、すべての部分文字列が回文で、各判定は中央まで進みます。文字の比較回数は約 n³/12 ≈ 6.7 × 10^8 回です。
アルゴリズム
- 最初の1文字を最善のものとし、開始位置を0、長さを1にします。
- 各開始位置
iと各終了位置j ≥ iについて、文字が異なるかポインターが出会うまで、両端から中央に向かって文字を比較します。 - 不一致がないままポインターが出会った場合、
s[i..j]は回文です。 - その長さ
j-i+1が最善の長さを上回る場合、iとその長さを記録します。 - 最善の開始位置と長さを使って部分文字列を返します。
def longestPalindrome(s):
n = len(s)
best_start, best_len = 0, 1
for i in range(n):
for j in range(i, n):
# Compare s[i..j] from both ends toward the middle
left, right = i, j
while left < right and s[left] == s[right]:
left += 1
right -= 1
is_palindrome = left >= right
if is_palindrome and j - i + 1 > best_len:
best_start, best_len = i, j - i + 1
return s[best_start:best_start + best_len]長さ別の回文表
考え方
ブルートフォースは学習したことを忘れてしまいます。"anana"を調べるとき、aとaを比較し、次にnとnを比較しますが、2回目の比較はすでに実行した"nan"全体の検査です。作業を省くルールは次のとおりです。s[i..j]は、両端が一致し、その間の部分s[i+1..j-1]が回文なら回文です。比較を1回行い、答えを1つ保存するだけで、各部分文字列を判定できます。
答えをテーブルpal[i][j]に保存し、長さごとに埋めていきます。1文字だけの部分文字列はすべて回文です。2文字の部分文字列は、両方の文字が一致すれば回文です。それより長い場合は、このルールを使います。内側の部分文字列は2文字短いため、そのセルはすでに埋まっています。
"bananas"では、pal[1][5]（"anana"）は、s[1]とs[5]がどちらもaで、pal[2][4]（"nan"）がtrueなのでtrueです。長さは小さい方から大きい方へ進み、開始位置は左から右へ進むため、新しい最長記録となる回文のうち最初に見つかるものは、その長さの中で最も左にある回文でもあります。約n²/2個のセルそれぞれにO(1)のコストがかかるため、時間計算量はO(n²)です。その代わりにメモリが必要で、n = 2000の場合は4 × 10^6個のセルを使います。
アルゴリズム
- すべて false の n × n テーブル
palを作ります。 - 長さを 1 から n まで変えながら、終端
j = i+length-1が文字列内に収まる各開始位置iについて、両端の文字を確認します。 - 両端が一致し、長さが 2 以下、または
pal[i+1][j-1]が true の場合、pal[i][j]に印を付けます。 - 印の付いたセルの長さがこれまでの最長を上回る場合、
iと長さを記録します。 - 最長の開始位置から部分文字列を返します。
def longestPalindrome(s):
n = len(s)
# pal[i][j] is True when s[i..j] reads the same both ways
pal = [[False] * n for _ in range(n)]
best_start, best_len = 0, 1
for length in range(1, n + 1):
for i in range(n - length + 1):
j = i + length - 1
# Equal ends, and the part inside them is a palindrome (or too short to matter)
if s[i] == s[j] and (length <= 2 or pal[i + 1][j - 1]):
pal[i][j] = True
if length > best_len:
best_start, best_len = i, length
return s[best_start:best_start + best_len]すべての中心を基準に拡大する
考え方
すべての回文には中心があります。"anana"のような奇数長の回文では中心は1文字で、"abba"のような偶数長の回文では中心は中央の2文字の間の隙間です。長さnの文字列にはn個の文字とn-1個の隙間があるため、中心の候補は2n-1個です。
中心から、両側の文字が一致する間、左右に1文字ずつ外側へ進みます。進むたびに、2文字長い回文があることが確かめられます。最初に文字が一致しなくなったとき、または文字列の端に達したときに探索を終えます。それより長い回文が同じ中心を持つことはありません。長くするには、一致しなかった文字の組を含むことになるからです。したがって、中心ごとに外側へ1回探索すればその中心を囲む最長の回文が見つかり、その中で最長のものが答えになります。
"bananas"では、インデックス3の文字aから始めます。インデックス2と4の文字はどちらもnで、インデックス1と5の文字はどちらもaです。インデックス0と6の文字はbとsなので、長さ5で探索を終えます。開始位置は3 - (5-1)/2 = 1で、これにより"anana"が得られます。同じ式center - (length-1)/2を切り捨てて使えば、隙間を中心とする場合にも機能します。
中心を左から右へ探索し、現在の最長より厳密に長い場合にのみ最良の結果を更新します。同じ長さの回文は偶奇が同じで、中心がより左にある回文ほど開始位置も左になるため、最も左にある回文が選ばれます。最悪の場合は、同じ文字が繰り返される文字列です。各中心から近い方の端まで探索するため、n = 2000の場合、約n²/2 = 2 × 10^6回のステップが必要になり、メモリ使用量は整数数個分です。
アルゴリズム
expand(left, right)を作成します。両方のインデックスが文字列の範囲内にあり、文字が一致する間、leftを1つ減らし、rightを1つ増やします。right-left-1を返します。- 0からn-1までの各中心について、
expand(center, center)とexpand(center, center+1)の大きい方を取得します。 - その長さが現在の最長の長さを超える場合、最長の開始位置を
center - (length-1)/2を切り捨てた値に設定し、最長の長さをその長さに設定します。 - 最長の開始位置から最長の長さ分の部分文字列を返します。
def expand(s, left, right):
# Grow outward while the two ends match; return the palindrome's length
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return right - left - 1
def longestPalindrome(s):
best_start, best_len = 0, 1
for center in range(len(s)):
# Odd lengths grow from one letter, even lengths from the gap after it
length = max(expand(s, center, center), expand(s, center, center + 1))
if length > best_len:
best_start = center - (length - 1) // 2
best_len = length
return s[best_start:best_start + best_len]
落とし穴と境界ケース
考え方はシンプルですが、バグは細部に潜んでいます。偶数文字列の中心、走査後の長さ、同じ長さの場合のルール、そして部分文字列の切り出しです。
- 文字の周りだけを中心に展開すると、偶数長の回文をすべて見逃します。
"abba"では、"abba"ではなく"a"が返されます。 - 走査は両端をそれぞれ1つ越えたところで止まるため、回文は
s[left+1..right-1]で、長さはright-left-1です。right-left+1を使うと、一致しない文字が2つ加わります。 - 長さが同じ場合に最良の結果を置き換えると、右端の回文が返されます。
"xyzzyabba"の場合、"yzzy"ではなく"abba"が返されます。 - 隙間を中心にする場合、
center - length/2では左に1つずれます。"xyzzyabba"では、インデックス2の後の隙間を中心とする長さ4の回文の開始位置は2 - (4-1)/2 = 1であり、0ではありません。 - 部分文字列の切り出しAPIは言語によって異なります。C++の
substrとC#のSubstringは長さを受け取りますが、JavaScriptのsubstringとJavaのsubstringは終了インデックスを受け取ります。 - 表を開始位置0から順に行を埋めていくと、
pal[i+1][j-1]が埋められる前に読み取られてしまいます。長さ順に埋めるか、開始位置を後ろから順にたどってください。
よくある質問4
最長回文部分文字列の時間計算量は何ですか？
中心を軸に広げる方法は、時間計算量が O(n²)、追加メモリの計算量が O(1) です。テーブルを使う方法も時間計算量は O(n²) ですが、メモリの計算量は O(n²) であり、すべての部分文字列を調べる方法は O(n³) です。Manacher のアルゴリズムなら O(n) を実現できますが、面接でこれを期待されることはほとんどありません。
なぜ中心を起点に拡張する方法では、2n-1 個の中心を使うのでしょうか？
奇数長の回文には中央の文字があり、偶数長の回文には同じ文字2つの間に中央の隙間があります。n文字の文字列にはn個の文字と、隣り合う文字の間にn-1個の隙間があります。文字だけを起点に広げると、"abba"のような回文を見逃します。
Manacherのアルゴリズムとは何ですか？
すべての中心の周りで最長の回文を、全体で O(n) の時間で見つけます。これまでで最も右まで伸びている回文を保持し、その中にある中心は、鏡映位置にある中心の答えから探索を始めるため、文字を最初から比較し直すことはありません。名前を覚えておく価値があります。「中心から展開する」は、面接官が通常求める解法です。
最長回文部分文字列は、最長回文部分列とどのように異なりますか？
部分文字列は連続する文字の並びですが、部分列では文字を飛ばすことができます。"character"では、最長の回文部分文字列は"ara"ですが、"carac"は長さ5の回文部分列です。部分列の問題は、両端が異なる場合に片端を除く(i, j)上の表を使って解きます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def longestPalindrome(s):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
s = "bananas"
期待値
"anana"