Cambios mínimos necesarios para generar substrings continuas de 0 y 1

Dada una string binaria S de longitud N , la tarea es encontrar el número mínimo de cambios de bit necesarios para convertir la string dada de manera que contenga solo substrings continuas de 0 y 1, de modo que la string final tenga la forma de 000. 000 , 111..111 , 111…000 o 000…111 .

Ejemplos: 

Entrada: S = 000100101, N = 9 
Salida: 2 
Explicación: 
000 1 00 1 01 -> 000 0 00 0 01

Entrada: S = 01100, N = 5 
Salida: 1 
Explicación:  
0 1100 -> 1 1100

Enfoque: 
el número mínimo de vueltas se puede calcular de manera eficiente en dos recorridos lineales. 
En el primer recorrido, calcularemos cuál puede ser el número mínimo de lanzamientos necesarios en el peor de los casos, ya que puede ser igual al número de 0 totales inicialmente . 
En el segundo recorrido, en cada paso, el número total de vueltas requeridas será la suma del total de 1 antes de ese punto y el total de 0 después de ese punto. Tomaremos un mínimo de todos los valores calculados en cada paso. 

Por lo tanto, para resolver el problema, siga los pasos a continuación: 

• Inicialice las variables cuenta0 = 0, cuenta1 = 0 y res = 0. donde, cuenta0 almacena la cuenta de 0 y cuenta1 almacena la cuenta de 1 y res almacena los cambios de bit requeridos.
• Recorra la string de entrada, calcule los 0 y guárdelo en la variable res.
• Recorra la string de entrada y reste el recuento de 0 si se encuentra el carácter 0 y almacene el recuento del carácter 1 en la variable count1 y actualice el res como min(res, count0+count1) .

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

// C++ implementation of the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
int minChanges(string str, int N)
{
    int res;
    int count0 = 0, count1 = 0;
 
    // Traverse input string
    // and store the count of 0
    for (char x : str) {
        count0 += (x == '0');
    }
    res = count0;
 
    // Traverse the input string again
    // to find minimum number of flips
    for (char x : str) {
        count0 -= (x == '0');
        count1 += (x == '1');
        res = min(res, count1 + count0);
    }
 
    return res;
}
 
// Driver code
int main()
{
    int N = 9;
    string str = "000101001";
 
    cout << minChanges(str, N);
    return 0;
}

// Java implementation of the above approach
import java.io.*;
 
class GFG{
 
static int minChanges(String str, int N)
{
    int res;
    int count0 = 0, count1 = 0;
 
    // Traverse input string
    // and store the count of 0
    for(char x : str.toCharArray())
    {
       if (x == '0')
           count0++;
    }
    res = count0;
 
    // Traverse the input string again
    // to find minimum number of flips
    for(char x : str.toCharArray())
    {
       if (x == '0')
           count0--;
       if (x == '1')
           count1++;
            
       res = Math.min(res, count1 + count0);
    }
    return res;
}
 
// Driver code
public static void main(String[] args)
{
    int N = 9;
    String str = "000101001";
 
    System.out.println(minChanges(str, N));
}
}
 
// This code is contributed by offbeat

# Python3 implementation of the above approach
def minChanges(str, N):
     
    count0 = 0
    count1 = 0
     
    # Traverse input string
    # and store the count of 0
    for x in str:
        count0 += (x == '0')
 
    res = count0
             
    # Traverse the input string again
    # to find minimum number of flips
    for x in str:
        count0 -= (x == '0')
        count1 += (x == '1')
        res = min(res, count1 + count0)
         
    return res
 
 
# Driver code
N = 9
str = "000101001"
 
print(minChanges(str, N))
 
# This code is contributed by shubhamsingh10

// C# implementation of the above approach
using System;
 
class GFG{
 
static int minChanges(String str, int N)
{
    int res;
    int count0 = 0, count1 = 0;
 
    // Traverse input string
    // and store the count of 0
    for(int i = 0; i < str.Length; i++)
    {
        if (str[i] == '0')
            count0++;
    }
    res = count0;
 
    // Traverse the input string again
    // to find minimum number of flips
    for(int i = 0; i< str.Length; i++)
    {
        if (str[i] == '0')
            count0--;
        if (str[i] == '1')
            count1++;
                 
        res = Math.Min(res, count1 + count0);
    }
    return res;
}
 
// Driver code
public static void Main()
{
    int N = 9;
    String str = "000101001";
 
    Console.Write(minChanges(str, N));
}
}
 
// This code is contributed by chitranayal

<script>
 
// Javascript implementation of the above approach
 
function minChanges(str, N)
{
    var res;
    var count0 = 0, count1 = 0;
 
    // Traverse input string
    // and store the count of 0
    str.split('').forEach(x => {
         
        count0 += (x == '0');
    });
    res = count0;
 
    // Traverse the input string again
    // to find minimum number of flips
    str.split('').forEach(x => {
         
        count0 -= (x == '0');
        count1 += (x == '1');
        res = Math.min(res, count1 + count0);
    });
 
    return res;
}
 
// Driver code
var N = 9;
var str = "000101001";
document.write( minChanges(str, N));
 
</script>

2

Complejidad temporal: O(k) , donde k es la longitud de la string binaria. 
Complejidad del espacio: O(1)