Zenn
🍅

【Python】最長回文部分文字列(longest palindromic substring)

に公開
Python
tech

最長回文部分文字列について

こんにちは！アルゴリズムの勉強において、最長回文部分文字列を求める問題について触れる機会があったので、まとめていきたいと思います。まず、最長回文部分文字列とは、与えられた文字列の中で、部分文字列であり、かつ回文で最長のものです。例えば、babadなら最長回文部分文字列は "bab" または "aba"です。要は、最長の回文を見つけ出せ！ということです。

アプローチの仕方

今回はいろんな解き方がある中で今回は、中心展開法（Expand Around Center） で解いていこうと思います。中心展開法（Expand Around Center） は、left と right の2つのポインタを使って、回文の中心から左右に広げていきます。回文には中心が存在し、そこを基準に左右対称になっているという特徴があります。そこで 「すべての文字を回文の中心として扱い、左右に拡張」 すれば、最長の回文を求められます。
詳しくは以下にまとめます。

アルゴリズムの流れ

  1. 文字列の各位置（インデックス）を回文の中心とする
  2. 左右同時に拡張しながら最大の回文を探す
  3. 最も長い回文を記録する
  4. すべての位置で試して、最長の回文を出力する

left と right の動き

  1. left と right を回文の中心に置く
  2. s[left] == s[right] ならば広げる
  3. 条件を満たさなくなったら終了
  4. その時点での最大回文を記録

なんかむずそうなので具体例を用いて考える。

例1: s = "babad"

例えば、i = 2（s[2] = "b"）を中心に考える。

  1. ステップ1：left = right = 2

    • s[2] = "b"
    • チェック: s[2] == s[2]
    • 拡張: left -= 1, right += 1（left = 1, right = 3）

  2. ステップ2：left = 1, right = 3

    • s[1] = "a", s[3] = "a"
    • チェック: s[1] == s[3]
    • 拡張: left -= 1, right += 1（left = 0, right = 4）

  3. ステップ3：left = 0, right = 4

    • s[0] = "b", s[4] = "d"
    • チェック: s[0] != s[4]（NG）

終了 → 最大回文 "aba" を記録。

例2: s = "cbbd"

  1. ステップ1：left = 1, right = 2
    • s[1] = "b", s[2] = "b"
    • チェック: s[1] == s[2]
    • 拡張: left -= 1, right += 1（left = 0, right = 3）
  2. ステップ2：left = 0, right = 3
    • s[0] = "c", s[3] = "d"
    • チェック: s[0] != s[3]
    • 終了 → 最大回文 "bb" を記録

まとめ

  • leftは 左に動く (left -= 1)
  • right は 右に動く (right += 1)
  • s[left] == s[right] なら 回文の範囲を広げる
  • 条件が崩れたらストップして記録

pythonで書いてみる

class Solution: #Solution クラスを定義。
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return ""  #入力が空文字列 "" の場合、回文も空になるのでそのまま返す。
        
        start, max_length = 0, 1
        
        def expand_around_center(left: int, right: int):
            nonlocal start, max_length #start と max_length を関数の外の変数として参照できるようにする。
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            
            if max_length < right - left - 1:
                start = left + 1
                max_length = right - left - 1
        
        for i in range(len(s)):
            expand_around_center(i, i)     # 奇数長の回文
            expand_around_center(i, i + 1) # 偶数長の回文
        
        return s[start:start + max_length]

# テスト
solution = Solution()
print(solution.longestPalindrome("babad"))  # "bab" または "aba"
print(solution.longestPalindrome("cbbd"))   # "bb"

Discussion