Pythonで2つの文字列から辞書順最大のマージ文字列を生成するプログラム

問題の概要

2つの文字列 s と t が与えられます。これらを使って「マージ」と呼ばれる新しい文字列を、次のルールで作成します。s または t のどちらかが空になるまで、以下のいずれかの操作を選んで繰り返します。

• s が空でない場合： s の先頭の1文字をマージ結果の末尾に追加し、その文字を s から取り除きます。
• t が空でない場合： t の先頭の1文字をマージ結果の末尾に追加し、その文字を t から取り除きます。

このとき、作成可能なマージの中で辞書順（lexicographical order）で最も大きい文字列を求めるのが目的です。

具体例

たとえば、s = "zxyxx"、t = "yzxxx" が入力された場合、出力は zyzxyxxxxx になります。選択の過程は以下の通りです。

• s から選択 → merge = "z"、s = "xyxx"、t = "yzxxx"
• t から選択 → merge = "zy"、s = "xyxx"、t = "zxxx"
• t から選択 → merge = "zyz"、s = "xyxx"、t = "xxx"
• s から選択 → merge = "zyzx"、s = "yxx"、t = "xxx"
• s から選択 → merge = "zyzxy"、s = "xx"、t = "xxx"

この後、s と t に残った5個の "x" をすべてマージ結果の末尾に連結して完成です。

解法のポイント：貪欲法と接尾辞の比較

この問題は貪欲法（Greedy法）で解くことができます。各ステップで「今選べる2文字のうち、より大きな方」を選べばよいのですが、注意点があります。両者の先頭文字が同じ場合、どちらを選んでもよいわけではありません。ここで重要になるのが「残りの部分文字列（接尾辞）同士の比較」です。

先頭文字が等しい場合は、接尾辞が辞書順で大きい側の文字列から文字を取ることで、常に最適な結果が得られます。後続の文字列が大きいほど、その文字を先に使うことで全体の並びを有利にできるためです。

アルゴリズムの手順

• 答えを格納する空文字列 ans を用意します。
• ポインタ idx1 と idx2 をそれぞれ 0 で初期化します。
• idx1 が s の長さ未満、かつ idx2 が t の長さ未満である間、次を繰り返します。
  • s[idx1] > t[idx2]、または（s[idx1] == t[idx2] かつ s[idx1:] >= t[idx2:]）の場合：
    ans に s[idx1] を連結し、idx1 を1増やします。
  • 上記以外の場合：
    ans に t[idx2] を連結し、idx2 を1増やします。
• ループ終了後、ans に s の残り（s[idx1:]）と t の残り（t[idx2:]）を連結して返します。

Pythonでの実装例

以下のコードで、実際の動作を確認してみましょう。

def solve(s, t):
   ans = ""
   idx1 = idx2 = 0
   while(idx1<len(s) and idx2<len(t)):
      if s[idx1]>t[idx2] or (s[idx1]==t[idx2] and s[idx1:]>=t[idx2:]):
         ans+=s[idx1]
         idx1+=1
      elif s[idx1]<t[idx2] or (s[idx1]==t[idx2] and s[idx1:]<=t[idx2:]):
         ans+=t[idx2]
         idx2+=1

   return ans+s[idx1:]+t[idx2:]

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

入力

s = "zxyxx", t = "yzxxx"

出力

zyzxyxxxxx

計算量について

ループ内でスライス s[idx1:] や t[idx2:] の比較を行うため、最悪の場合の時間計算量は O((|s| + |t|)²) となります。ただし、実際の動作では多くの場合これより高速に処理され、文字列長が数千程度であれば十分実用的な速度で動作します。