C++で特別なバイナリ文字列を辞書順最大に変換する方法

本記事では、「特別なバイナリ文字列」と呼ばれる特殊な性質を持つ文字列を、任意回数の操作によって辞書順で最大の文字列へと変換する問題を、C++を用いて解説します。

特別なバイナリ文字列とは

まず、対象となる「特別なバイナリ文字列」は、以下の2つの性質を満たします。

• 文字列中の 0 と 1 の個数が等しい
• 文字列の任意の接頭辞（先頭から始まる部分列）において、1 の出現数が常に 0 の出現数以上である

問題の定義

特別な文字列 S に対して行える「操作」は次のように定義されます。

S から連続する2つの非空な特別な部分文字列を選び、それらを入れ替える。

この操作を何度でも繰り返してよいとき、最終的に得られる文字列の中で辞書順最大のものを求めるのが本問題の目的です。

入力例と出力例

たとえば、入力が 11011000 の場合、出力は 11100100 となります。これは、部分文字列 "10" と "1100" を入れ替えることで得られる、操作後の辞書順最大の文字列だからです。

アルゴリズムの考え方

この問題は、再帰的な分解と貪欲法（グリーディー法）を組み合わせることで効率的に解けます。手順は以下の通りです。

1. 関数 makeLargestSpecial(s) を定義し、結果を格納する空文字列 ret と、部分文字列を保持する配列 v を用意します。
2. カウンタ cnt を使って文字列を走査します。'1' なら cnt を +1、'0' なら -1 します。
3. cnt が 0 になった時点で、その区間は「バランスの取れた特別な部分文字列」とみなせます。このとき、両端の '1' と '0' を除いた内部部分に対して再帰的に makeLargestSpecial を呼び出し、結果を "1" + 内部の最適化結果 + "0" の形で配列 v に追加します。
4. 配列 v を降順にソートします。これにより、より大きいブロックが前方に配置され、辞書順最大の結果が得られます。
5. ソート済みの要素をすべて連結して返します。

このアプローチの鍵は、各バランス区間を独立した単位として扱い、それらを降順に並べ替えることで全体の辞書順を最大化できる点にあります。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    string makeLargestSpecial(string s) {
        string ret = "";
        vector<string> v;
        int i = 0;
        for (int j = 0, cnt = 0; j < s.size(); j++) {
            if (s[j] == '1') {
                cnt++;
            }
            else
            cnt--;
            if (cnt == 0) {
                v.push_back("1" + makeLargestSpecial(s.substr(i + 1,
                j - i - 1)) + "0");
                i = j + 1;
            }
        }
        sort(v.rbegin(), v.rend());
        for (int i = 0; i < v.size(); i++)
        ret += v[i];
        return ret;
    }
};
main(){
    Solution ob;
    cout << (ob.makeLargestSpecial("11011000"));
}

実行結果

入力

11011000

出力

11100100

まとめ

本問題では、特別なバイナリ文字列を再帰的にバランス区間へ分解し、各区間を内部で最適化した上で降順ソート・連結することで、辞書順最大の文字列を求めました。計算量は文字列長を n とすると O(n² log n) 程度となり、実用的な範囲で十分高速に動作します。再帰構造と貪欲法の組み合わせは、類似の文字列変換問題にも応用できる有用なテクニックです。