問題定義

最も長い回文部分文字列とは、対称的な構造を持つ文字列のことです。例えば、文字列 s = "ababd" の場合、"aba" や "bab" が回文として該当します。

解決方針

最初の考えでは、括弧のマッチングのようなアプローチを使用し、スタックで要素を「ペア消去」することで回文を判定しようと考えました。しかし実際には「対称軸」の位置が固定されておらず、前方の消去処理が後続の比較に影響を与えることが判明しました。

その後、回文の対称性には2つのパターンがあることに気づきました。奇数長の対称性（例："abcba"）と偶数長の対称性（例："abccba"）で、それぞれ異なる処理方法が必要です。

このような背景から、以下の解決策を採用しました：

1. 基準となる位置を軸として設定し、奇数型と偶数型（左側ポイントとして扱う）の両戦略に基づいて回文を探索します。両方見つかった場合はより長い方を選択します（例："bccca" では "cc" と "ccc" が存在し、"ccc" を返します）。
2. 文字列全体を走査し、各位置を軸としてすべての回文部分文字列を収集してリストを作成します。
3. 結果のリストを確認し、最も長い回文を返却します。

実装コード

### 特定インデックスを軸とする回文検索 - 偶数長パターン（例："abba"）

from typing import Optional, List

def find_even_palindrome_at_position(text: str, center_pos: int) -> Optional[str]:
    """文字列text内でcenter_posを軸とする対称文字列を検索 - 偶数長パターン（左側ポイントとして使用）"""
    if center_pos < 1:
        return None
    
    max_displacement = min(center_pos, len(text) - center_pos)
    
    displacement = 1
    while displacement < max_displacement:
        left_char, right_char = text[center_pos - (displacement - 1)], text[center_pos + displacement]
        if left_char != right_char:
            break
        displacement += 1
    
    if displacement > 1:
        displacement -= 1
        return text[center_pos - (displacement - 1):center_pos + displacement + 1]
    return None

### 特定インデックスを軸とする回文検索 - 奇数長パターン（例："abcba"）

def find_odd_palindrome_at_position(text: str, center_pos: int) -> Optional[str]:
    """文字列text内でcenter_posを軸とする対称文字列を検索 - 奇数長パターン"""
    if center_pos < 1:
        return None
    
    max_displacement = min(center_pos, len(text) - center_pos)
    
    displacement = 1
    while displacement < max_displacement:
        left_char, right_char = text[center_pos - displacement], text[center_pos + displacement]
        if left_char != right_char:
            break
        displacement += 1
    
    if displacement > 1:
        displacement -= 1
        return text[center_pos - displacement:center_pos + displacement + 1]
    return None

### 両パターンを統合し、特定位置を軸とする最も長い回文を取得

def find_longest_palindrome_at_position(text: str, center_pos: int) -> Optional[str]:
    """文字列text内でcenter_posを軸とする最も長い回文を返す - 両戦略を統合"""
    result_even = find_even_palindrome_at_position(text, center_pos)
    result_odd = find_odd_palindrome_at_position(text, center_pos)
    
    if result_even is None:
        return result_odd
    if result_odd is None:
        return result_even
    
    return result_even if len(result_even) > len(result_odd) else result_odd

### 文字列内のすべての回文部分文字列を検索

def collect_all_palindromes(text: str) -> List[str]:
    """すべての回文部分文字列を収集"""
    palindrome_list = []
    for position in range(1, len(text) - 1):
        found_palindrome = find_longest_palindrome_at_position(text, position)
        if found_palindrome is not None:
            palindrome_list.append(found_palindrome)
    return palindrome_list

### すべての回文の中から最も長いものを選択

def find_maximum_palindrome(text: str) -> Optional[str]:
    """最も長い回文部分文字列を検索"""
    all_palindromes = collect_all_palindromes(text)
    if not all_palindromes:
        return None
    
    return max(all_palindromes, key=len)

### テストコード

if __name__ == '__main__':
    print(find_maximum_palindrome('ababd'))
    print(find_maximum_palindrome('aaabacccababa'))
    print(find_maximum_palindrome('aaabaccababa'))

注：このアルゴリズムの時間計算量は約O(n²)であり、最適な解法ではありません

from typing import Optional, List


def find_even_palindrome_at_position(text: str, center_pos: int) -> Optional[str]:
    """文字列text内でcenter_posを軸とする対称文字列を検索 - 偶数長パターン（左側ポイントとして使用）"""
    if center_pos < 1:
        return None
    
    max_displacement = min(center_pos, len(text) - center_pos)
    
    displacement = 1
    while displacement < max_displacement:
        left_char, right_char = text[center_pos - (displacement - 1)], text[center_pos + displacement]
        if left_char != right_char:
            break
        displacement += 1
    
    if displacement > 1:
        displacement -= 1
        return text[center_pos - (displacement - 1):center_pos + displacement + 1]
    return None


def find_odd_palindrome_at_position(text: str, center_pos: int) -> Optional[str]:
    """文字列text内でcenter_posを軸とする対称文字列を検索 - 奇数長パターン"""
    if center_pos < 1:
        return None
    
    max_displacement = min(center_pos, len(text) - center_pos)
    
    displacement = 1
    while displacement < max_displacement:
        left_char, right_char = text[center_pos - displacement], text[center_pos + displacement]
        if left_char != right_char:
            break
        displacement += 1
    
    if displacement > 1:
        displacement -= 1
        return text[center_pos - displacement:center_pos + displacement + 1]
    return None


def find_longest_palindrome_at_position(text: str, center_pos: int) -> Optional[str]:
    """文字列text内でcenter_posを軸とする最も長い回文を返す - 両戦略を統合"""
    result_even = find_even_palindrome_at_position(text, center_pos)
    result_odd = find_odd_palindrome_at_position(text, center_pos)
    
    if result_even is None:
        return result_odd
    if result_odd is None:
        return result_even
    
    return result_even if len(result_even) > len(result_odd) else result_odd


def collect_all_palindromes(text: str) -> List[str]:
    """すべての回文部分文字列を収集"""
    palindrome_list = []
    for position in range(1, len(text) - 1):
        found_palindrome = find_longest_palindrome_at_position(text, position)
        if found_palindrome is not None:
            palindrome_list.append(found_palindrome)
    return palindrome_list


def find_maximum_palindrome(text: str) -> Optional[str]:
    """最も長い回文部分文字列を検索"""
    all_palindromes = collect_all_palindromes(text)
    if not all_palindromes:
        return None
    
    return max(all_palindromes, key=len)


if __name__ == '__main__':
    print(find_maximum_palindrome('ababd'))
    print(find_maximum_palindrome('aaabacccababa'))
    print(find_maximum_palindrome('aaabaccababa'))