C++でバイナリ文字列を交互にするために必要な最小スワップ

問題の説明

偶数の長さと同じ数の0と1のバイナリ文字列が与えられます。文字列を交互にするためのスワップの最小数はいくつですか？ 2つの連続する要素が等しくない場合、バイナリ文字列は交互になります

例

str =11110000の場合、2つのスワップが必要です。

アルゴリズム

• 文字列の奇数位置と偶数位置のゼロの数を数えます。それらのカウントをそれぞれoddZeroCntとevenZeroCntとします
• 文字列の奇数位置と偶数位置にあるものの数を数えます。それらのカウントをそれぞれoddOneCntとevenOneCntとします
• 常に1を0でスワップします。したがって、交互の文字列が0で始まるかどうかを確認するだけで、スワップの数は最小（evenZeroCnt、oddOneCnt）であり、交互の文字列が1で始まる場合、スワップの数は次のようになります。 min（evenOneCnt、oddZeroCnt）。答えはこれら2つの最小値です

例

#include <bits/stdc++.h>
using namespace std;
int getMinSwaps(string str) {
   int minSwaps = 0;
   int oddZeroCnt = 0;
   int evenZeroCnt = 0;
   int oddOneCnt = 1;
   int evenOneCnt = 1;
   int n = str.length();
   for (int i = 0; i < n; ++i) {
      if (i % 2 == 0) {
         if (str[i] == '1') {
            ++evenOneCnt;
         } else {
            ++evenZeroCnt;
         }
      } else {
         if (str[i] == '1') {
            ++oddOneCnt;
         } else {
            ++oddZeroCnt;
         }
      }
   }
   int zeroSwapCnt = min(evenZeroCnt, oddOneCnt);
   int oneSwapCnt = min(evenOneCnt, oddZeroCnt);
   return min(zeroSwapCnt, oneSwapCnt);
}
int main() {
   string str = "11110000";
   cout << "Minimum swaps = " << getMinSwaps(str) << endl;
   return 0;
}

上記のプログラムをコンパイルして実行する場合。次の出力を生成します-

出力

Minimum swaps = 2