Minimum swaps required to make a binary string alternating in C++

Problem statement

Given a binary string of even length and equal number of 0’s and 1’s. What is the minimum number of swaps to make the string alternating? A binary string is alternating if no two consecutive elements are equal

Example

If str = 11110000 then 2 swaps are required.

Algorithm

• Count number of zeroes at odd position and even position of the string. Let their count be oddZeroCnt and evenZeroCnt respectively
• Count number of ones at odd position and even position of the string. Let their count be oddOneCnt and evenOneCnt respectively
• We will always swap a 1 with a 0. So we just check if our alternating string starts with 0 then the number of swaps is min (evenZeroCnt, oddOneCnt) and if our alternating string starts with 1 then the number of swaps is min (evenOneCnt, oddZeroCnt). The answer is min of these two

Example

 Live Demo

#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; }

When you compile and execute above program. It generates following output −

Output

Minimum swaps = 2