Pythonで文字列を1回だけ回転させた後に得られる最長回文（パリンドローム）部分文字列の長さを求める方法

問題概要

文字列 s が与えられ、この文字列は任意の位置でちょうど1回だけ回転できるものとします。この操作を行った結果として得られる、最長の回文（パリンドローム）部分文字列の長さを求めるのが目的です。

たとえば、入力が s = "elklev" の場合を考えてみましょう。「el」と「klev」の間で回転すると「levelk」という文字列が得られます。このとき最長の回文部分文字列は「level」であり、その長さは 5 となります。

解法のアプローチ

この問題は、以下の手順で解くことができます。

• s2 := 文字列 s を2回連結した文字列を作る
• max_len := 0 で初期化する
• x を 0 から s の長さ - 1 まで繰り返す：
  • y を 0 から s の長さまで繰り返す：
    • temp := s2 のインデックス x から x + y までの部分文字列
    • temp が回文であり、かつその長さが max_len より大きい場合：
      • max_len := temp の長さ
• max_len を返す

このアプローチのポイントは、文字列を2倍に連結することで、考えられるすべての回転パターンを s2 の部分文字列として表現できる点にあります。あとは各部分文字列が回文かどうかを順番にチェックし、最も長いものを記録していくだけです。

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

class Solution:
   def solve(self, s):
      s2 = 2 * s
      max_len = 0
      for x in range(len(s)):
         for y in range(len(s) + 1):
            temp = s2[x : x + y]
            if temp == temp[::-1] and len(temp) > max_len:
               max_len = len(temp)
      return max_len

ob = Solution()
s = "elklev"
print(ob.solve(s))

入力

"elklev"

出力

5

計算量について

この解法では、開始位置と長さの組み合わせが O(n²) 通り存在し、さらにそれぞれの回文判定に O(n) の時間がかかるため、全体の時間計算量は O(n³) となります。短い文字列であれば十分実用的ですが、より長い入力を扱う場合は、Manacherのアルゴリズムなどを活用して回文判定を高速化する工夫も検討するとよいでしょう。