Minimum Characters to be Removed to Make a Binary String Alternate

Problem Statement

Given a binary string, write a program that will find the minimum number of characters that can be removed from this string so that it becomes alternate. A binary string is said to be alternate if there are no consecutive 0’s or 1’s

Input Format

The first line containing the string “s”.

Output Format

The first line contains an integer value which represents the number of characters to be removed to make a binary string alternate.

Constraints

• 1<=|s|<=10^6
• s[i] is either 0 or 1

Example

0011

2

Explanation: In the given string “0011” we need to remove one zero and one 1 one to make it alternate.

Algorithm

1. Traverse the given string s from left to right.

2. If the current char is different from the next char then simply move to the next index.

3. Else, we need to delete one character.

Implementation

C++ Program for Minimum Characters to be Removed to Make a Binary String Alternate

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

int main()
{
   string s;
   cin>>s;
   int n=s.length();
   int ans=0;
   for(int i=0;i<n-1;i++)
   {
       if(s[i]==s[i+1])
       {
           ans++;
       }
   }
   cout<<ans<<endl;
   return 0;
}

import java.util.Scanner;

class sum
{ 
  public static void main(String[] args) 
  { 
    Scanner sr = new Scanner(System.in); 
                String s = sr.next();
                char a[] = s.toCharArray();
    int n = s.length();
                int ans=0;
                for(int i=0;i<n-1;i++)
                {
                    if(a[i]==a[i+1])
                    {
                        ans++;
                    }
                }
                System.out.println(ans);
  } 
} 

00011101

4

Here we do not use any auxiliary space so the space complexity is O(1). Simply here we declare one integer variable which stores the number of characters to be removed to make a binary string alternate.