Pythonで文字列内のすべての回文部分文字列が奇数長かどうかを判定する方法

問題の概要

文字列 s が与えられたとき、その中に含まれるすべての回文（palindrome）部分文字列の長さが奇数であるかどうかを判定します。偶数長の回文部分文字列がひとつでも存在すれば False を返し、存在しなければ True を返します。

例えば、s = "levelopmadam" の場合、回文部分文字列として "level"（5文字）と "madam"（5文字）があり、どちらも奇数長なので、出力は True になります。

解法のアプローチ

基本的な考え方は、文字列から取り得るすべての部分文字列を生成し、「長さが偶数で、かつ回文になっているもの」が存在するかどうかを順番にチェックしていくというものです。手順は以下の通りです。

• i を 0 から文字列の長さまで繰り返す
  • temp に空文字列を代入する
  • j を i から文字列の長さまで繰り返す
    • temp に s[j] を連結する
    • temp の長さが偶数で、かつ temp が回文であれば False を返す
• すべてのループが完了したら True を返す

実装例

def is_palindrome(s):
    return s == s[::-1]

def solve(s):
    for i in range(len(s)):
        temp = ""
        for j in range(i, len(s)):
            temp += s[j]
            if len(temp) % 2 == 0 and is_palindrome(temp):
                return False
    return True

s = "levelopmadam"
print(solve(s))

入力

"levelopmadam"

出力

True

コードの解説

is_palindrome 関数は、スライス s[::-1] を使って文字列を反転させ、元の文字列と一致するかどうかで回文判定を行っています。Pythonらしい簡潔な書き方です。

solve 関数では、二重の for ループによって開始位置 i と終了位置 j のすべての組み合わせを試し、temp に文字を一つずつ追加しながら部分文字列を作成しています。長さが偶数の部分文字列だけを回文判定の対象とすることで、不要な計算を減らしています。

計算量について

この方法はすべての部分文字列を調べるため、時間計算量は O(n³) になります（部分文字列の生成に O(n²)、それぞれの回文判定に O(n)）。文字列が長くなると処理時間が急激に増大する点に注意が必要です。

より効率的な最適化手法

実は、この問題には O(n) で解けるエレガントな性質があります。偶数長の回文部分文字列が存在するとき、必ず「隣り合う2文字が等しい」箇所が存在するのです。これは、偶数長の回文の中央にある2文字が互いに鏡像の関係にあり、必ず同じ文字になるためです。

したがって、隣接する文字のペアを一度走査するだけで判定できます。

def solve_fast(s):
    return all(s[i] != s[i + 1] for i in range(len(s) - 1))

s = "levelopmadam"
print(solve_fast(s))  # True

例えば "abba" のような偶数長の回文には "bb" という同じ文字のペアが含まれていますが、"level" のような奇数長の回文にはそのようなペアがありません。この性質を利用すれば、ごく短いコードで高速に判定できます。