Minimum Characters to be Removed to Make a Binary String Alternate

Difficulty Level Easy
Frequently asked in Coursera Fourkites Hike MAQ o9 solutions Pocket Gems Taxi4Sure
StringViews 1622

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

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

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

Complexity Analysis

Time Complexity

O(n) where n is the size of the given string “s”. Here we simply traverse the string and check if the current char is equal to the next char. If it’s equal then increase the ans otherwise move to the next index.

Space Complexity

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.

Translate ยป