【Python】1回のスワップで作れる辞書式順序で最小の文字列を求める方法

問題の概要

文字列 s が与えられたとき、文字列内の2つの文字を最大1回だけ入れ替える（スワップする）ことで得られる、辞書式順序で最も小さい文字列を求めます。

例えば、入力が "zyzx" の場合、出力は "xyzz" となります。最初の文字 z を x と入れ替えることで、辞書式順序で最小の文字列が得られます。

解法のアプローチ

この問題を解くために、以下の手順に従います。

• temp：文字列 s と同じサイズの配列を作成し、0で初期化します。
• m：文字列の長さから1を引いた値（末尾のインデックス）で初期化します。
• i を文字列の末尾から先頭へ向かってループさせます。
  • s[i] < s[m] の場合、m = i と更新します。
  • temp[i] = m を記録します。これにより、「位置 i 以降で最も小さい文字のインデックス」が各位置ごとに保存されます。
• 次に、i を先頭から末尾までループさせます。
  • a = temp[i] とします。
  • s[a] が s[i] と異なる場合、i 番目と a 番目の文字を入れ替えた結果の文字列を返します。
• どの入れ替えでも文字列が改善されない場合は、元の文字列 s をそのまま返します。

実装例

class Solution:
    def solve(self, s):
        temp = [0]*len(s)
        m = len(s)-1
        for i in range(len(s)-1, -1, -1):
            if s[i]<s[m]: m=i
            temp[i] = m
        for i in range(len(s)):
            a = temp[i]
            if s[a] != s[i]:
                return s[:i]+s[a]+s[i+1:a]+s[i]+s[a+1:]
        return s
ob = Solution()
print(ob.solve("zyzx"))

入力

zyzx

出力

xyzz

アルゴリズムのポイント

このアルゴリズムの鍵は、右側から事前走査を行う点にあります。末尾から順に処理することで、「各位置より後ろにある最小の文字」のインデックスを temp 配列に効率的に記録できます。

その後、先頭から走査し、現在の文字よりも小さい文字が後方に存在する最初の位置を見つけたら、そこを入れ替えます。これにより、できるだけ前方の文字を小さくすることができ、結果として辞書式順序で最小の文字列が得られます。

計算量は前走査・後走査ともに線形時間であるため、全体の時間計算量は O(n)、空間計算量も補助配列分の O(n) となり、非常に効率的な解法です。