Pythonで文字列から辞書式順序で最大の回文部分列を見つける方法

問題の概要

文字列Sが与えられたとき、その文字列から辞書式順序で最大の回文(パリンドローム)部分列を見つけることを考えます。

例えば、入力が「tutorialspointtutorial」の場合、出力は「uu」となります。

解決のアプローチ

この問題は一見複雑に思えますが、実は非常にシンプルな性質を利用することで効率的に解けます。その鍵となるのは、辞書式順序で最大の回文部分列は、文字列に含まれる最大の文字だけで構成されるという点です。

理由は以下の通りです。

• 任意の1文字は、それ自体が回文です。
• 同じ文字を繰り返した文字列も、必ず回文になります。
• したがって、文字列中の最大文字をすべて集めたものが、辞書式順序で最大の回文部分列となります。

アルゴリズムの手順

• ans(答え)を空文字列として初期化します。
• max_val を s[0](最初の文字)で初期化します。
• i を 1 から文字列の長さまで繰り返し、max_val を max_val と s[i] のうち大きい方で更新します。
• i を 0 から文字列の長さまで繰り返し、s[i] が max_val と等しい場合は ans に s[i] を追加します。
• 最後に ans を返します。

実装例

以下にPythonでの実装例を示します。

def largest_palindromic_substr(s):
    ans = ""
    max_val = s[0]
    for i in range(1, len(s)):
        max_val = max(max_val, s[i])
    for i in range(0, len(s)):
        if s[i] == max_val:
            ans += s[i]
    return ans

s = "tutorialspointtutorial"
print(largest_palindromic_substr(s))

入力と出力

入力:

"tutorialspointtutorial"

出力:

uu

コードの解説

最初のループでは文字列全体を走査し、辞書式順序で最大の文字(この例では「u」)を見つけます。続く2番目のループでは、その最大文字と一致するすべての文字を連結して結果を組み立てます。「tutorialspointtutorial」には「u」が2つ含まれているため、出力は「uu」となり、これが求める回文部分列です。

このアルゴリズムの計算量はO(n)であり、文字列を2回走査するだけで済むため、非常に効率的です。動的計画法などを用いる必要がない点も、この手法の大きな利点といえるでしょう。