Pythonで辞書順最小の非回文文字列を求めるプログラムを解説

問題の概要

回文（パリンドローム）である文字列 s が与えられます。このうちちょうど1文字を別の文字に置き換えて、結果が回文にならないようにし、かつその文字列が辞書順で最小になるようにします。

たとえば、入力が s = "level" の場合、出力は "aevel" になります。先頭の "l" を "a" に置き換えることで、回文ではなくなり、かつ辞書順で最小の文字列が得られるためです。

解き方のアプローチ

辞書順を最小にするには、できるだけ前方の位置の文字を、できるだけ小さい文字（"a"）へ置き換えるのが基本です。ただし、すでに "a" になっている文字を "a" に変えても文字列は変わりません。そこで、次の手順で処理を行います。

• 文字列の前半（インデックス 0 ～ len(s) // 2 - 1）を先頭から走査します。
• "a" 以外の文字が見つかったら、その文字を "a" に置き換えて結果を返します。
• 前半がすべて "a" の場合は、末尾の1文字を "b" に置き換えて返します。

前半だけを調べるのは、回文では前半と後半が鏡像の関係にあるため、前半の1文字を変えれば必ず回文が崩れるからです。また、前半がすべて "a" のケース（例："aba" や "aaa"）では、中央や後半の "a" をいくら変えても回文のままになってしまうため、末尾を "b" に変えるのが最善となります。

実装例

以下がPythonでの実装です。

class Solution:
    def solve(self, s):
        for i in range(len(s) // 2):
            if s[i] != "a":
                s = list(s)
                s[i] = "a"
                return "".join(s)
        s = list(s)
        s[-1] = "b"
        return "".join(s)

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

入力

"level"

出力

aevel

計算量について

前半の走査には O(n/2)、文字列とリストの相互変換や結合には O(n) のコストがかかるため、全体の時間計算量は O(n) です。追加メモリについても、リスト変換の分だけ O(n) が必要になります。