Pythonで2つの文字列をマージして最大の文字列を作成する方法

問題の概要

2つの文字列「a」「b」と、空の文字列「merge」が与えられているとします。この課題では、次のルールに従って「merge」を文字で埋めていきます。

• 文字列「a」が空でない場合、「a」の先頭の1文字を取り除き、それを「merge」に追加します。
• 文字列「b」が空でない場合、「b」の先頭の1文字を取り除き、それを「merge」に追加します。
• 両方の文字列が空でない場合は、辞書順で比較し、大きい方の文字列から先頭の1文字を取り出して「merge」に追加します。つまり「a」が「b」より大きければ先に「a」から、そうでなければ「b」から文字を取り出します。
• これをどちらかの文字列が空になるまで繰り返します。
• 最後に、完成した文字列「merge」を返します。

入力例

a = "bacaa"
b = "abcaa"

出力

bacabcabaa

解説

最初に「a」（"bacaa"）と「b」（"abcaa"）を比較すると、「a」の方が辞書順で大きいため、「a」の先頭文字「b」を取り出します。その後も毎回残りの文字列同士を比較し、大きい方の先頭文字を順に「merge」へ追加していくことで、最終的に「bacabcabaa」が得られます。

解き方のアプローチ

この問題は貪欲法（グリーディ法）で解くのが効果的です。各ステップで残りの文字列「a」と「b」を丸ごと辞書順に比較し、大きい方の先頭の1文字を「merge」に連結していきます。文字列全体を比較することで、先頭の文字が同じ場合でも、その後ろに続く文字の並びを見て、どちらから取るべきかを正しく判断できます。

• 2つの入力文字列「a」と「b」を受け取ります。
• 関数 concatenate_largest(a, b) は、2つの文字列を引数に取り、マージ後の最大の文字列を返します。
• 「a > b」なら「a」の先頭1文字を結果に追加し、「a」を1文字短くします。
• 「a < b」なら「b」の先頭1文字を結果に追加し、「b」を1文字短くします。
• どちらかが空になったらループを抜け、残りの文字列を末尾に連結して返します。

Pythonでの実装例

def concatenate_largest(a, b):
    ans = ""
    while a and b:
        if a > b:
            ans += a[0]
            a = a[1:]
        else:
            ans += b[0]
            b = b[1:]
    ans += a
    ans += b
    return ans

a = "bacaa"
b = "abcaa"
print(concatenate_largest(a, b))

上記のコードを実行すると、次の出力が得られます。

出力

bacabcabaa

2つの文字列「bacaa」と「abcaa」は、このルールに従ってマージすると「bacabcabaa」になります。

計算量について

各ステップの文字列比較には最大で O(m+n) の時間がかかるため（m、n はそれぞれの文字列の長さ）、全体の時間計算量は O((m+n)²) となります。一方、結果の文字列を格納するための空間計算量は O(m+n) です。