Pythonで解く「最長チャンク回文分解」― 両端からの貪欲法アルゴリズム

問題の概要

ある文字列 text が与えられたとき、次の条件をすべて満たす最大の k を求める問題です。

• 各 a[i](i = 1〜k)は空でない文字列である
• 連結した a[1] + a[2] + ... + a[k] が、与えられた text と完全に一致する
• すべての i について a[i] = a[k+1-i] が成り立つ(前後のチャンクが対称になっている)

たとえば、入力が "antaprezatepzapreanta" の場合、出力は 11 になります。これは次のように11個のチャンクへ分割できるためです。

(a)(nt)(a)(pre)(za)(tpe)(za)(pre)(a)(nt)(a)

解き方のアプローチ

この問題は、文字列の両端から同時に走査する貪欲法(グリーディ法)で効率的に解けます。左端から伸ばしていく部分文字列 temp1 と、右端から伸ばしていく部分文字列 temp2 が一致したタイミングで、そのペアを1組としてカウントしていきます。

アルゴリズムの手順

1. start := 0、end := 文字列長 - 1 と初期化します。
2. temp1 と temp2 を空文字列で初期化します。
3. ans を、文字列長が奇数なら 1、偶数なら 0 に設定します。
4. start < end の間、以下を繰り返します。
   • temp1 := temp1 + text[start]
   • temp2 := text[end] + temp2
   • temp1 と temp2 が一致したら、両方を空文字列にリセットし、ans := ans + 2 とします。
   • start := start + 1、end := end - 1
5. 文字列長が偶数で、かつ temp1 または temp2 が空でない場合は、ans := ans + 1 とします。
6. ans を返します。

Pythonでの実装例

以下のコードで実際の動作を確認できます。

class Solution(object):
    def longestDecomposition(self, text):
        start = 0
        end = len(text) - 1
        temp1 = ""
        temp2 = ""
        ans = 1 if len(text) & 1 else 0
        while start < end:
            temp1 += text[start]
            temp2 = text[end] + temp2
            if temp1 == temp2:
                temp1 = temp2 = ""
                ans += 2
            start += 1
            end -= 1
        if len(text) % 2 == 0 and (temp1 or temp2):
            ans += 1
        return ans

ob = Solution()
print(ob.longestDecomposition("antaprezatepzapreanta"))

入力

"antaprezatepzapreanta"

出力

11

まとめ

このアルゴリズムは、左右から1文字ずつ付け足しながら一致を判定するシンプルな貪欲法です。一致した時点でできるだけ早く分割を確定させることで、最大のチャンク数を得られます。最悪計算量は O(n²) となりますが、実装が非常に分かりやすく、LeetCode の「Longest Chunked Palindrome Decomposition」のような文字列操作系の問題にもそのまま応用できる考え方です。