Pythonで文字列に偶数長の回文（パリンドローム）部分文字列が含まれるかどうかを判定する方法

文字列 s が与えられたとき、その文字列の中に偶数の長さを持つ回文（パリンドローム）が含まれているかどうかを判定する問題を考えてみましょう。

例えば、入力が s = "afternoon" の場合、出力は True になります。これは「afternoon」という文字列の中に、偶数長の回文である「noon」が含まれているためです。

解き方のポイント

この問題には重要な性質があります。それは、偶数長の回文は必ず中央に「同じ文字が隣り合うペア」を持つという点です。

例えば「noon」の場合、中央の2文字は「oo」であり、同じ文字が連続しています。つまり、文字列内を先頭から順に走査し、隣接する2文字が一致している箇所が1つでも存在すれば、その文字列には偶数長の回文が含まれていると判断できます。

アルゴリズムの手順

• i を 0 から「文字列の長さ - 2」まで繰り返します。
• string[i] と string[i + 1] が同じ文字であれば、True を返します。
• ループが終了しても一致するペアが見つからなければ、False を返します。

この方法なら、時間計算量 O(n)・空間計算量 O(1) という非常に効率的な解法になります。

実装例

それでは、実際のPythonコードを見てみましょう。

def solve(string):
    for i in range(len(string) - 1):
        if string[i] == string[i + 1]:
            return True
    return False

s = "afternoon"
print(solve(s))

入力

"afternoon"

出力

True

注意点

ループ範囲は必ず range(len(string) - 1) としましょう。range(len(string)) のままにすると、最後の要素で string[i + 1] を参照した際に IndexError が発生してしまいます。

まとめ

偶数長の回文の存在確認は、「隣接する同じ文字のペアがあるか」を調べるだけで十分です。このシンプルな発想により、線形時間で問題を解くことができます。ぜひ自分のコードにも応用してみてください。