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 stringvoid 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 Codeint 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 approachimport 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 stringdef 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 stringstr = "01011100"# Length of the stringN = len(str)# Prints the minimum count# of operations requiredminOps(str, N)# This code is contributed by sanjoy_62. |
C#
// C# program for the above approachusing 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:
2
Time Complexity: O(N)
Auxiliary Space: O(1)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
