Strings: Minimum Number of Swaps to Make the Binary String Alternating

Problem Statement:

You are given a binary string of 0s and 1s. You need to get the minimum steps to make the string alternating.

Example

Input: s = “111000”
Output: 1

Swap elements at s[1] and s[4] to make the string alternating.

Solution

In the solution, we count the number of characters that are misplaced and return the count.

Solution in C++

#include <algorithm>  
#include <iostream>    
#include <string>
#include <stack>
#include <vector>
#include <unordered_map> 
#include <queue> 

using namespace std;

int min_fill_pos(string& s, char ch, int current = 0) 
{
    int count = 0;
    for(int i=0; i<s.size(); i+=2) 
    {
        if(s[i] != ch) count++;
    }
    return count;
}
    
int min_swaps_required(string s) 
{
    //check if the difference between 1s and 0s is greater than 1
    int oneCount = count(s.begin(), s.end(), '1');
    int zeroCount = count(s.begin(), s.end(), '0');
    if(abs(oneCount-zeroCount) > 1) return -1;

    // if 1s count is greater than 0, check the misplaced character count
    // for ex: 011. Here 1s > 0s count.
    // only possible solution is 101. So, starting from 0th index, check 
    // for misplaced character at every i+2th position.
    // same for 0
    if(oneCount > zeroCount) 
      return min_fill_pos(s,'1');
    if(zeroCount > oneCount) return 
      min_fill_pos(s,'0');

    return min(min_fill_pos(s,'0'), min_fill_pos(s,'1'));
}

int main() 
{ 
      
string s1 = "111000"; 
 
cout<<"The min swaps required are "<<min_swaps_required(s1)<<endl;

return 0; 
} 

Output:

The min swaps required are 1