Segregate 1s and 0s in separate halves of a Binary String

0 0 4 minutes read

Given a binary string str of even length, consisting of equal number of 0s and 1s, the task is to segregate all 1s and 0s into separate halves by repeatedly reversing a substring. Print the minimum count of reversals required.

Examples:

Input: str = “01011100”
Output: 2
Explanation: The operations performed are as follows:

“01011100″ -> “11101000”

“11101000″ -> “11110000”

Input: str = “101010”
Output: 2
Explanation: The operations performed are as follows:

“101010″ -> “110100”

“110100″ -> “111000”

Approach: The idea is to count the number of instances in which any two consecutive characters of the string are unequal. Follow the steps below to solve the problem:

Initialize a variable, say ans, to count the number of adjacent unequal pair of characters.
Now, after reversing any substring, the count reduces by 2.
If the value of ans is odd, then the required answer will be (ans – 1)/2, as the final string will contain one such pair at the center of the string.
Otherwise, the required answer is ans/2.

Below is the implementation of the above approach:

C++14

#include <bits/stdc++.h>
using namespace std;
 
// Function to count the minimum number
// of operations required to segregate
// all 1s and 0s in a binary string
void minOps(string s, int N)
{
   
    // Stores the count of unequal
    // pair of adjacent characters
    int ans = 0;
    for (int i = 1; i < N; i++)
    {
 
        // If an unequal pair of
        // adjacent characters occurs
        if (s[i] != s[i - 1]) 
        {
            ans++;
        }
    }
 
    // For odd count
    if (ans % 2 == 1) 
    {
        cout << (ans - 1) / 2 << endl;
        return;
    }
 
    // For even count
    cout<<(ans / 2);
}
 
// Driver Code
int main()
{
   
  // Given string
  string str = "01011100";
 
  // Length of the string
  int N = str.size();
 
  // Prints the minimum count
  // of operations required
  minOps(str, N);
 
  return 0;
}
 
// This code is contributed by mohit kumar 29

Java

// Java program for the above approach
 
import java.io.*;
import java.util.*;
 
class GFG {
 
    // Function to count the minimum number
    // of operations required to segregate
    // all 1s and 0s in a binary string
    static void minOps(String s, int N)
    {
        // Stores the count of unequal
        // pair of adjacent characters
        int ans = 0;
 
        for (int i = 1; i < N; i++) {
 
            // If an unequal pair of
            // adjacent characters occurs
            if (s.charAt(i) != s.charAt(i - 1)) {
                ans++;
            }
        }
 
        // For odd count
        if (ans % 2 == 1) {
            System.out.print((ans - 1) / 2);
            return;
        }
 
        // For even count
        System.out.print(ans / 2);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Given string
        String str = "01011100";
 
        // Length of the string
        int N = str.length();
 
        // Prints the minimum count
        // of operations required
        minOps(str, N);
    }
}

Python3

# Python 3 implementation of above approach 
 
# Function to count the minimum number
# of operations required to segregate
# all 1s and 0s in a binary string
def minOps(s, N) :
   
    # Stores the count of unequal
    # pair of adjacent characters
    ans = 0
    for i in range(1, N):
 
        # If an unequal pair of
        # adjacent characters occurs
        if (s[i] != s[i - 1]) :
            ans += 1
         
    # For odd count
    if (ans % 2 == 1) :      
        print((ans - 1) // 2)
        return
     
    # For even count
    print(ans // 2)
 
# Driver Code
 
# Given string
str = "01011100"
 
# Length of the string
N = len(str)
 
# Prints the minimum count
# of operations required
minOps(str, N)
 
# This code is contributed by sanjoy_62.

C#

// C# program for the above approach
using System;
public class GFG 
{
 
    // Function to count the minimum number
    // of operations required to segregate
    // all 1s and 0s in a binary string
    static void minOps(String s, int N)
    {
       
        // Stores the count of unequal
        // pair of adjacent characters
        int ans = 0;
 
        for (int i = 1; i < N; i++)
        {
 
            // If an unequal pair of
            // adjacent characters occurs
            if (s[i] != s[i - 1]) 
            {
                ans++;
            }
        }
 
        // For odd count
        if (ans % 2 == 1)
        {
            Console.Write((ans - 1) / 2);
            return;
        }
 
        // For even count
        Console.Write(ans / 2);
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
       
        // Given string
        String str = "01011100";
 
        // Length of the string
        int N = str.Length;
 
        // Prints the minimum count
        // of operations required
        minOps(str, N);
    }
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// JavaScript program for the above approach
 
    // Function to count the minimum number
    // of operations required to segregate
    // all 1s and 0s in a binary string
    function minOps( s , N) 
    {
        // Stores the count of unequal
        // pair of adjacent characters
        var ans = 0;
 
        for (i = 1; i < N; i++) {
 
            // If an unequal pair of
            // adjacent characters occurs
            if (s.charAt(i) != s.charAt(i - 1)) {
                ans++;
            }
        }
 
        // For odd count
        if (ans % 2 == 1) {
            document.write((ans - 1) / 2);
            return;
        }
 
        // For even count
        document.write(ans / 2);
    }
 
    // Driver Code
     
        // Given string
        var str = "01011100";
 
        // Length of the string
        var N = str.length;
 
        // Prints the minimum count
        // of operations required
        minOps(str, N);
 
// This code contributed by aashish1995
 
</script>

Output:

Time Complexity: O(N)
Auxiliary Space: O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!