C++でバイナリ文字列から「01」「10」のペアを削除！必要な最小削除回数を求める方法

このチュートリアルでは、バイナリ文字列（0と1のみで構成される文字列）から「01」および「10」のペアをすべて取り除くために必要な削除回数の合計を求めるC++プログラムを紹介します。まずは具体例を見てみましょう。

入力 − 101010001

出力 − 4

上記の例では、「01」と「10」のペアをすべて文字列から除去するために、合計4回の削除が必要になります。

すべてのペアを削除した後に残る文字列は 0 です。

解法の考え方

バイナリ文字列から「01」と「10」のペアをすべて削除するということは、隣り合う異なる文字（0と1）を順番に取り除いていくことを意味します。この操作を繰り返すと、最終的に残るのはどちらか一方の文字だけです。

したがって、削除が必要なペアの総数は、0の個数と1の個数のうち小さい方、すなわち min(count(0), count(1)) となります。

問題を解くための手順は以下の通りです。

• バイナリ文字列を初期化します。

• 文字列内の0と1の個数をそれぞれカウントします。

• 0の個数と1の個数のうち、小さい方を出力します。

サンプルコード

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
int findMinimumNumberOfDeletions(string str, int len) {
   int zeroes_count = 0, ones_count = 0;
   // 0と1の個数をカウント
   for (int i = 0; i < len; i++) {
      if (str[i] == '0') {
         zeroes_count++;
      }
      else {
         ones_count++;
      }
   }
   return min(zeroes_count, ones_count);
}
int main() {
   string str = "101010001";
   int len = str.length();
   cout << findMinimumNumberOfDeletions(str, len) << endl;
   return 0;
}

実行結果

上記のプログラムを実行すると、次のような結果が得られます。

4

まとめ

このように、文字列中の0と1の出現回数を数えて小さい方を選ぶだけで、O(n) の計算量で効率的に答えを求められます。本チュートリアルについて質問がある場合は、コメント欄でお気軽にお知らせください。