Pythonで2つの文字列の辞書順最大のマージを求めるプログラム

問題の概要

2つの文字列 s と t が与えられます。次のルールに従って、新しい文字列「merge」を構築します。s または t のどちらか一方でも空でない限り、以下の操作のいずれかを選択して繰り返します。

• s が空でない場合：s の先頭の1文字を merge の末尾に追加し、その文字を s から削除します。
• t が空でない場合：t の先頭の1文字を merge の末尾に追加し、その文字を t から削除します。

最終的に、この方法で作成できる文字列の中から辞書順で最大のものを見つけます。

たとえば、入力が s = "zxyxx"、t = "yzxxx" の場合、出力は "zyzxyxxxxx" になります。

解き方：貪欲法

この問題は貪欲法（greedy法）で解くことができます。各ステップで、s の残りの部分 s[a:] と t の残りの部分 t[b:] を文字列として比較し、辞書順で大きい方の先頭の文字を merge に追加していきます。

ここで重要なのは、先頭の1文字だけを比べるのではなく、残りの文字列全体（接尾辞）を比較するという点です。同じ文字で始まる場合でも、その後の文字の並びによって最適な選択は変わります。接尾辞全体を見ることで、将来の選択肢まで考慮した判断が可能になり、常に正しい結果にたどり着けます。

アルゴリズムの手順

• ポインタ a と b を 0 で初期化し、merge を空文字列にします。
• W1 = len(s)、W2 = len(t) を求めます。
• a < W1 かつ b < W2 の間、以下を繰り返します。
  • s[a:] > t[b:] の場合：merge に s[a] を連結し、a を 1 増やします。
  • それ以外の場合：merge に t[b] を連結し、b を 1 増やします。
• ループを抜けたら、merge + s[a:] + t[b:] を返します。

最後に残りの文字列をまとめて連結するのは、片方の文字列が空になった時点では、もう片方の残りをすべて追加するのが常に最適だからです。

Pythonでの実装例

以下の実装を見ると、処理の流れがより理解しやすくなります。

def solve(s, t):
   a = b = 0
   merge = ""

   W1 = len(s)
   W2 = len(t)
   while a < W1 and b < W2:
      if s[a:] > t[b:]:
         merge += s[a]
         a += 1
      else:
         merge += t[b]
         b += 1

   return merge + s[a:] + t[b:]

s = "zxyxx"
t = "yzxxx"
print(solve(s, t))

入力

"zxyxx", "yzxxx"

出力

zyzxyxxxxx

計算量について

各ステップで接尾辞同士の比較には最大で O(n) の時間がかかるため、全体の計算量は最悪ケースで O(n²) となります。文字列長がそれほど大きくない場合には十分実用的で、ロジックもシンプルなので理解しやすいのが特徴です。