C++でバイナリ文字列から最小の正しい文字列を求める方法を解説

n ビットの2進数文字列 S があるとします。ただし、余分な先頭のゼロは含まれていないものとします。この文字列 S に対して、次の2種類の操作を実行することができます。

• 隣接する任意の2ビットを入れ替える
• すべての「11」を「1」に置き換える

val(S) を S の10進数表現とします。そして、正しい文字列 A が別の正しい文字列 B よりも小さいとは、val(A) < val(B) が成り立つときであると定義します。この条件下で、最小の正しい文字列を求めるのが本問題の目的です。

具体例

たとえば、入力が S = "1001" の場合を考えてみましょう。このときの出力は「100」となります。次のような一連の操作によって実現できるためです。

"1001" → "1010" → "1100" → "100"

解法の考え方

まず、なぜこのような答えになるのかを考察してみましょう。

「隣接するビットを入れ替える」操作により、実質的に好きな位置へビットを移動させることが可能です。つまり、すべての「0」を先頭の「1」の後ろへ集めることができます。

さらに、「11」を「1」に置き換える操作を繰り返し適用することで、先頭の1つ目の「1」を除くすべての「1」を消去できます。

したがって、最小の正しい文字列は「先頭の1」+「残りの部分に含まれるすべての0」という構成になります。これが数値として最小となる文字列です。

アルゴリズムの手順

この問題を解くために、以下の手順に従います。

• n := 文字列 S の長さとする
• res := 空の文字列を用意し、S[0] を追加する(先頭は必ず「1」)
• i = 1 から n - 1 までループを実行する:
  • S[i] が '0' である場合、res に "0" を連結する
• 最後に res を返す

C++による実装例

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

#include <bits/stdc++.h>
using namespace std;
string solve(string S){
    int n = S.size();
    string res = "";
    res += S[0];
    for (int i = 1; i < n; i++){
        if (S[i] == '0'){
            res += "0";
        }
    }
    return res;
}
int main(){
    string S = "1001";
    cout << solve(S) << endl;
}

入力

"1001"

出力

100

このアルゴリズムの計算量は O(n) であり、文字列の長さに比例した効率的な処理が可能です。ビットの入れ替え操作を実際にシミュレーションする必要がなく、0の個数を数えるだけで答えが求まる点がポイントです。