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

2つの文字列「a」と「b」、および結果を格納するための文字列「merge」が与えられているとします。この課題は、次のルールに従って「a」と「b」から1文字ずつ取り出し、「merge」を埋めていくことです。

• 文字列「a」が空でない場合、「a」の先頭の1文字を取り除き、その文字を「merge」に追加します。
• 文字列「b」が空でない場合、「b」の先頭の1文字を取り除き、その文字を「merge」に追加します。
• 両方の文字列が空でない場合は、それぞれの残りの文字列を辞書順に比較し、より大きい方の先頭文字を「merge」へ移します。たとえば「a」が「b」より大きい場合は、先に「a」から文字を取り出します。
• どちらかの文字列が空になるまで操作を繰り返し、完成した文字列「merge」を返します。

入力例と出力例

入力:

a = "bacaa"
b = "abcaa"

出力:

bacabcaaaa

解説:

最初の比較では、文字列「a」（bacaa）が文字列「b」（abcaa）よりも辞書順で大きいため、「a」の先頭文字「b」を取り出します。以降も同様に、毎回残りの文字列同士を比較して大きい方の先頭文字を「merge」に移していくことで、最終的に「bacabcaaaa」という辞書順で最大のマージ文字列が得られます。

この問題を解くためのアプローチ

この問題は再帰を使うことで簡潔に解くことができます。各ステップで文字列「a」と「b」の残り部分を辞書順に比較し、大きい方（または等しい場合）の先頭の1文字を「merge」に連結していきます。ここでのポイントは、先頭の1文字だけでなく「残りの文字列全体」を比較対象にすることです。こうすることで、同じ文字が続くケースでも、その後の並びまで見て常に最適な選択ができるようになります。

• 2つの入力文字列「a」と「b」を受け取ります。
• 再帰関数 concatenateLargest(string a, string b) は、2つの文字列を引数として受け取り、マージ後の最大の文字列を返します。
• 両方の文字列が空の場合は、a + b を返して再帰を終了します。
• 文字列「a」が「b」以下の場合は、「b」の先頭文字を結果に連結し、残りの「b」を引数として自分自身を再帰呼び出しします。
• 文字列「a」が「b」より大きい場合は、「a」の先頭文字を結果に連結し、残りの「a」を引数として再帰呼び出しします。
• すべての文字を処理し終えたら、連結された文字列を返します。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
string concatenateLargest(string a, string b) {
    if (a.size() == 0 || b.size() == 0) {
        return (a + b);
    }
    if (a <= b)
        return b[0] + concatenateLargest(a, b.substr(1));
    else
        return a[0] + concatenateLargest(a.substr(1), b);
}
int main() {
    string a = "bacaa";
    string b = "abcaa";
    cout << concatenateLargest(a, b) << endl;
    return 0;
}

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

出力

bacabcaaaa

2つの文字列「bacaa」と「abcaa」は、このアルゴリズムに従ってマージすると「bacabcaaaa」になります。各ステップで残りの文字列全体を辞書順に比較することで、常に最適な文字を選択できているのがポイントです。