Pythonで文字の削除・並べ替えにより生成できる最長回文を求めるアルゴリズム

問題の概要

ある文字列が与えられたとき、そこから文字を削除または並べ替え（シャッフル）することで作成できる最長の回文を見つけることを考えます。候補となる回文が複数存在する場合は、そのうちの1つを返せば十分です。

例えば、入力が pqqprrs の場合、出力は pqrsrqp になります。

解き方の考え方

回文とは、前から読んでも後ろから読んでも同じになる文字列のことです。回文を構成するには、各文字が中心を基準に左右対称にペアで配置されている必要があり、最大で1文字だけ中央に単独で置くことができます。

この性質を利用すると、以下の手順で最長回文を構築できます。

1. サイズ256の配列 count を用意し、すべて0で初期化します。
2. 文字列の先頭から末尾まで走査し、各文字のASCIIコードに対応する count の要素を1ずつ増やして、出現回数を記録します。
3. 前半部分 begin、中央の文字 mid、後半部分 end の3つの空文字列を用意します。
4. 変数 character を 'a' のASCIIコードで初期化し、'z' に達するまで以下を繰り返します。
   • count[character] が奇数の場合：その文字を中央 mid として記録し、カウントを1減らしてから、同じ文字を偶数として再度処理できるようにポインタを1つ戻します。
   • count[character] が偶数の場合：出現回数の半分の数だけ、その文字を begin に追加します。
5. end を begin の逆順として設定します。
6. begin ＋ 中央の1文字 ＋ end を連結した結果を返します。

実装例

理解を深めるために、以下のPythonによる実装を見てみましょう。

def get_palindrome(string):
    count = [0]*256
    for i in range(len(string)):
        count[ord(string[i])] += 1
    begin = ""
    mid = ""
    end = ""
    character = ord('a')
    while character <= ord('z'):
        if (count[character] & 1):
            mid = character
            count[character] -= 1
            character -= 1
        else:
            for i in range(count[character]//2):
                begin += chr(character)
        character += 1
    end = begin
    end = end[::-1]
    return begin + chr(mid) + end

string = "pqqprrs"
print(get_palindrome(string))

入力

"pqqprrs"

出力

pqrsrqp

計算量について

このアルゴリズムの時間計算量は O(n) です（n は文字列の長さ）。文字の出現回数を数えるのに O(n)、26種類の英小文字を走査して結果を構築するのにも合計で O(n) しかかかりません。空間計算量も O(n) であり、結果の文字列を格納するために必要となります。