バイナリ文字列を交互文字列にするための最小フリップ回数をC++で求める方法

バイナリ文字列「10011」が与えられたとします。これを交互文字列（0と1が交互に並んだ文字列）にするためには、最小で2文字をフリップして「10101」にする必要があります。

交互文字列には2つのパターンが考えられます。「0」で始まるパターンと「1」で始まるパターンです。そこで、両方のパターンについて必要なフリップ回数をそれぞれカウントし、そのうちの最小値を返します。具体的な例を見てみましょう。

入力

binary = "10011"

出力

2

文字列を「0」で始まる交互文字列にする場合は3回のフリップが必要ですが、「1」で始まる場合は2回のフリップで済みます。したがって、最小値は2となります。

アルゴリズム

• バイナリ文字列を初期化します。
• 「1」で始まる交互文字列にするために必要なフリップ回数をカウントします。
• 同様に、「0」で始まる交互文字列にするために必要なフリップ回数をカウントします。
• 上記2つの結果から最小値を求めます。
• 最小値を出力します。

実装

以下は、上記のアルゴリズムをC++で実装したコードです。

#include <bits/stdc++.h>
using namespace std;
char flip(char binaryDigit) {
   return binaryDigit == '0' ? '1' : '0';
}
int getFlipCountToAlternateString(string binary, char expected) {
   int flipCount = 0;
   for (int i = 0; i < binary.length(); i++) {
      if (binary[i] != expected) {
         flipCount++;
      }
      expected = flip(expected);
   }
   return flipCount;
}
int main() {
   string binary = "10011";
   cout << min(getFlipCountToAlternateString(binary, '0'), getFlipCountToAlternateString(binary,       '1')) << endl;
   return 0;
}

出力

上記のコードを実行すると、次の結果が得られます。

2

このアルゴリズムの計算量は、文字列の長さをNとするとO(N)であり、非常に効率的です。各文字について期待される文字と比較し、一致しない場合はフリップ回数をインクリメントするだけなので、実装もシンプルです。