Separe los 1 y los 0 en mitades separadas de una string binaria

Dada una string binaria str de longitud uniforme, que consta del mismo número de 0 y 1 , la tarea es segregar todos los 1 y 0 en mitades separadas invirtiendo repetidamente una substring . Imprime el recuento mínimo de reversiones requeridas.

Ejemplos:

Entrada: str = “01011100”
Salida: 2
Explicación: Las operaciones realizadas son las siguientes: 

1. “ 010111 00″ -> “11101000”
2. “111 01 000″ -> “11110000”

Entrada: str = “101010”
Salida: 2
Explicación: Las operaciones realizadas son las siguientes: 

1. “1 0101 0″ -> “110100”
2. “11 01 00″ -> “111000”

Enfoque: la idea es contar el número de instancias en las que dos caracteres consecutivos cualesquiera de la string son desiguales. Siga los pasos a continuación para resolver el problema:

• Inicialice una variable, digamos ans , para contar el número de pares de caracteres desiguales adyacentes.
• Ahora, después de invertir cualquier substring, el conteo se reduce en 2 .
• Si el valor de ans es impar , entonces la respuesta requerida será (ans – 1)/2, ya que la string final contendrá uno de esos pares en el centro de la string.
• De lo contrario, la respuesta requerida es ans/2 .

A continuación se muestra la implementación del enfoque anterior:

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

# 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# 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

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

2

Complejidad temporal: O(N)
Espacio auxiliar: O(1)