Longest Palindromic Substring

アルゴリズム概要

問題説明

文字列 s が与えられたとき、最長の回文部分文字列を返す問題です。

入出力例

Input: s = "babad"
Output: "bab" (または "aba")

Input: s = "cbbd"
Output: "bb"

制約条件

• 1 <= s.length <= 1000
• s は英字と数字のみから構成される

戦略

• 中心展開法を使用し、各位置を中心として左右に展開
• 奇数長（中心1文字）と偶数長（中心2文字）の両方を試行
• 回文が続く限り範囲を広げ、最長のものを記録
• 追加メモリを使わず、インデックスのみで管理

主要ポイント

ステップバイステップ解説

s = "babad" を例に、アルゴリズムの動作を追ってみましょう。

Python実装

from __future__ import annotations


class Solution:
    def longestPalindrome(self, s: str) -> str:
        """
        Longest Palindromic Substring - 中心展開法
        Time: O(n^2), Space: O(1)

        各位置を中心に奇数長・偶数長の回文を展開し、最長のものを返す。
        """
        n: int = len(s)
        if n <= 1:
            return s

        def expand(l: int, r: int) -> tuple[int, int]:
            """
            中心 (l, r) から可能な限り展開し、
            inclusive の [L, R] インデックスを返す。
            """
            while l >= 0 and r < n and s[l] == s[r]:
                l -= 1
                r += 1
            # ループ終了時は l, r が条件を満たさない位置なので +1, -1 で戻す
            return l + 1, r - 1

        best_l: int = 0
        best_r: int = 0

        # 各位置で奇数長・偶数長の両方を試行
        for i in range(n):
            # 奇数長（中心1文字）
            l1, r1 = expand(i, i)
            if r1 - l1 > best_r - best_l:
                best_l, best_r = l1, r1

            # 偶数長（中心2文字）
            l2, r2 = expand(i, i + 1)
            if r2 - l2 > best_r - best_l:
                best_l, best_r = l2, r2

        # 最後に一度だけスライスを生成（メモリ効率化）
        return s[best_l : best_r + 1]

フローチャート

フローの説明：
1. 開始 → 文字列 s の長さをチェック
2. n ≤ 1 なら s をそのまま返して終了（基底条件）
3. そうでなければ best_l = 0, best_r = 0 で初期化
4. 各位置 i を走査（i = 0 から n-1 まで）
5. 各位置で expand(i, i) を実行（奇数長）
6. より長い回文なら best を更新
7. 次に expand(i, i+1) を実行（偶数長）
8. より長い回文なら best を更新
9. i++ して次の位置へ（ステップ4に戻る）
10. 全位置走査完了後、s[best_l : best_r+1] を返して終了

計算量分析