【C++】バイナリ文字列から「01」または「10」を削除する方法を解説

「01010110011」のようなバイナリ文字列に対して、隣接する「01」または「10」を繰り返し削除することを考えます。「01」や「10」が文字列から完全になくなるまで削除を行うとき、最大で何回削除できるかを求めるのが本問題です。この記事では、C++による効率的な解法をわかりやすく解説します。

アルゴリズムのポイント

「01」または「10」を1回削除するたびに、「0」と「1」が必ず1文字ずつ減少します。つまり、削除できる最大回数は文字列に含まれる「0」の個数と「1」の個数のうち小さい方（min）に等しくなります。この性質を利用すれば、実際に削除操作をシミュレートする必要はなく、各文字の出現回数を数えるだけで答えが求まります。

実装の流れ

まず、初期文字列を宣言してその長さを取得し、それらを deleteSubstr(str, length) 関数に渡します。

string str = "01010110011";
int length = str.length();
cout << "Count of substring deletion" << deleteSubstr(str, length);

deleteSubstr(string str, int length) 関数の内部では、for ループが i が length 未満である間実行され、文字が「0」なら変数 count_0 を、「1」なら変数 count_1 をそれぞれインクリメントしていきます。そして最後に、count_0 と count_1 の小さい方の値を返り値として返します。

int deleteSubstr(string str, int length){
    int count_0 = 0, count_1 = 0;
    for (int i = 0; i < length; i++) {
        if (str[i] == '0')
            count_0++;
        else
            count_1++;
    }
    return min(count_0, count_1);
}

サンプルコード

それでは、バイナリ文字列から「01」または「10」を削除して、これらを含まない文字列にする実装全体を見てみましょう。

#include <iostream>
using namespace std;
int deleteSubstr(string str, int length){
    int count_0 = 0, count_1 = 0;
    for (int i = 0; i < length; i++) {
        if (str[i] == '0')
            count_0++;
        else
            count_1++;
    }
    return min(count_0, count_1);
}
int main(){
    string str = "01010110011";
    int length = str.length();
    cout << "Count of substring deletion " << deleteSubstr(str, length);
    return 0;
}

出力結果

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

Count of substring deletion 5

入力例「01010110011」には「0」が5個、「1」が6個含まれているため、min(5, 6) = 5 となり、削除回数は5回となります。

計算量

文字列を一度走査するだけなので、時間計算量は O(n)、追加で必要なメモリは O(1) と非常に効率的です。