C++で連結文字列をループ状に分割し、辞書順最大の文字列を求める方法

問題の概要

文字列のリストが与えられ、これらをループ状につなぎ合わせることを考えます。このとき、各文字列はそのまま使うか反転するかを選択できます。考えられるすべてのループの中から、ループを1箇所切断して通常の文字列に戻したときに、辞書順で最大になる文字列を見つけるのが目的です。

具体的には、次の2つのフェーズを経て辞書順最大の文字列を求めます。

• 連結フェーズ：すべての文字列を1つのループに連結します。一部の文字列は反転しても構いませんが、並び順は与えられた順序のまま保ちます。
• 切断フェーズ：ループ上の任意の位置に切断点を1つ設け、その文字から始まる通常の文字列を作ります。生成可能なすべての文字列の中から、辞書順で最大のものを求めます。

入力例と出力例

たとえば、入力が「abc」「xyz」である場合、出力は「zyxcba」となります。作れるループ状の文字列は「-abcxyz-」「-abczyx-」「-cbaxyz-」「-cbazyx-」の4通りです（「-」はループのつながりを表しています）。答えは4番目のループから得られ、中央の文字「a」の位置で切断すると「zyxcba」が完成します。

解法のアプローチ

この問題を解く鍵となるのは、「最終的な答えの中で各文字列は、元の形か反転した形のどちらかで必ず現れる」という性質です。そこで、まず各文字列について元の文字列と反転した文字列を比較し、辞書順で大きい方に置き換えておきます。そのうえで、各文字列内の各位置を切断点として候補を生成し、最大のものを記録していきます。

手順1：solve() 関数の定義

インデックス idx、文字列配列 strs、反転フラグ rev を引数にとる関数 solve() を定義します。

1. temp := strs[idx] とし、rev が真であれば temp を反転します。
2. str1 := 空文字列、str2 := 空文字列で初期化します。
3. i := 0 から idx 未満まで繰り返し、str1 に strs[i] を連結します。
4. i := idx + 1 から strs のサイズ未満まで繰り返し、str2 に strs[i] を連結します。
5. k := 0 から temp のサイズ未満まで繰り返し、以下の処理を行います。
   • newOne := temp の k 番目以降の部分文字列 ＋ str2 ＋ str1 ＋ temp の先頭から k 文字分の部分文字列
   • ret が空、または ret ＜ newOne であれば、ret := newOne と更新します。

手順2：findMax() 関数の定義

文字列配列 strs を引数にとる関数 findMax() を定義します。各文字列について、元の文字列とそれを反転した文字列を比較し、辞書順で大きい方を strs[i] に代入します。これにより、以降の探索で各文字列は常に有利な向きで扱えます。

手順3：メイン処理

1. ret := 空文字列で初期化します。
2. findMax(strs) を呼び出します。
3. i := 0 から strs のサイズ未満まで、solve(i, strs, false) と solve(i, strs, true) を呼び出します。
4. ret を返します。

C++による実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    string ret;
    void solve(int idx, vector<string> strs, bool rev){
        string temp = strs[idx];
        if (rev)
            reverse(temp.begin(), temp.end());
        string str1 = "";
        string str2 = "";
        for (int i = 0; i < idx; i++)
            str1 += strs[i];
        for (int i = idx + 1; i < strs.size(); i++)
            str2 += strs[i];
        for (int k = 0; k < temp.size(); k++) {
            string newOne = temp.substr(k) + str2 + str1 + temp.substr(0, k);
            if (ret == "" || ret < newOne) {
                ret = newOne;
            }
        }
    }
    void findMax(vector<string>& strs){
        for (int i = 0; i < strs.size(); i++) {
            string temp = strs[i];
            reverse(temp.begin(), temp.end());
            strs[i] = strs[i] > temp ? strs[i] : temp;
        }
    }
    string splitLoopedString(vector<string>& strs) {
        ret = "";
        findMax(strs);
        for (int i = 0; i < strs.size(); i++) {
            solve(i, strs, false);
            solve(i, strs, true);
        }
        return ret;
    }
};
main(){
    Solution ob;
    vector<string> v = {"abc", "xyz"};
    cout << (ob.splitLoopedString(v));
}

実行結果

入力

{"abc", "xyz"}

出力

zyxcba

計算量の目安

文字列の本数を n、全文字数の合計を L とすると、切断点の候補は各文字列内の各文字の位置に相当し、候補ごとに長さ L の文字列を構築・比較する必要があります。そのため、時間計算量は O(n × L²) 程度となります。なお、この問題は LeetCode の「Split Concatenated Strings」（問題555）としても知られており、文字列操作と貪欲法の組み合わせを学ぶのに適した題材です。