find the Min flips required

Given a binary string, that is it contains only 0s and 1s. We need to make this string a sequence of alternate characters by flipping some of the bits, our goal is to minimize the number of bits to be flipped.




Example 1:

Input : str = “001”

Output : 1

Minimum number of flips required = 1

We can flip 1st bit from 0 to 1 to make alternate  

string “101”. 


Example 2:

Input : str = “0001010111”

Output : 2

Minimum number of flips required = 2

We can flip 2nd bit from 0 to 1 and 9th 

bit from 1 to 0 to make alternate  

string “0101010101”. 



method :

step 1:take two strings x and y,

step 2: if the string s="0001010111", than make x="0101010101" and y="1010101010"

step3: compare s with x and count the difference, similarly s with y count the difference

step 4: now the min of both the differences, is the output


c++ implementation:

#include <bits/stdc++.h>
using namespace std;

int main() {
  int t; cin>>t;
    while(t--) 
    {
        string s;cin>>s;
        
        int n=s.length();
        string x;string y;
        int f=0;
        
        for(int i=0;i<n;i++)
        {
            if(f==0)
            {
                x=x+'0';
                y=y+'1';
            }
            else
            {
                 x=x+'1';
                 y=y+'0';
            }
            
            f=!f;
        }
        
        int c=0;
        for(int i=0;i<n;i++)
            if(x[i]!=s[i])
            c++;
            
        int d=0;
        for(int i=0;i<n;i++)
            if(y[i]!=s[i])
            d++;
           
           
        cout<<min(c,d)<<endl; 
    }
    return 0;
}
Time Complexity: O(n)  ,where n is the length of the string



 

darkmode