Volteos mínimos requeridos para mantener todos los 1 juntos en una string binaria

Dada la string binaria str , la tarea es encontrar el número mínimo de vueltas requeridas para mantener todos los 1 juntos en la string binaria dada, es decir, no debe haber ningún 0 entre 1 en la string.

Ejemplos:  

Entrada: str = “0011111100” 
Salida: 0 
Explicación: No necesitamos cambiar ningún bit porque todos están agrupados y no hay cero entre dos.

Entrada: str = “11100111000101” 
Salida: 4 
Explicación: Podemos voltear el bit 4 y 5 para convertirlos en 1 y voltear el bit 12 y 14 para convertirlos en 0. Entonces, la string resultante es “11111111000000” con 4 cambios posibles. 
 

Enfoque: Para resolver el problema mencionado anteriormente implementaremos el enfoque de programación dinámica donde tendremos los siguientes estados:  

• El primer estado es dp[i][0] , que indica el número de vueltas necesarias para que todos los ceros lleguen al i-ésimo bit.
• Segundo estado dp[i][1] que significa el número de cambios necesarios para hacer que el bit actual sea 1 de modo que se cumplan las condiciones dadas en la pregunta.

Entonces, la respuesta requerida será cambios mínimos para hacer que el bit actual sea 1 + cambios mínimos para hacer que todos los bits después del bit actual sean 0 para todos los valores de i . Pero si todos los bits en la string dada son 0, entonces no tenemos que cambiar nada, por lo que podemos verificar el mínimo entre nuestra respuesta y el número de vueltas requeridas para hacer que la string solo tenga ceros. Entonces podemos calcular la respuesta iterando sobre todos los caracteres en la string donde, 

respuesta = min (respuesta, dp[i][1] + dp[n-1][0] – dp[i][0]) donde dp[
i
][1] = Número mínimo de cambios para configurar el bit actual 1
dp[n-1][0] – dp[i][0] = Número mínimo de giros requeridos para hacer que todos los bits después de i sean 0

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

//cpp implementation for Minimum number of
//flips required in a binary string such
//that all the 1’s are together
#include <bits/stdc++.h>
using namespace std;
int minFlip(string a)
{
     //Length of the binary string
    int n = a.size();
 
    vector<vector<int>> dp(n + 1,vector<int>(2, 0));
 
    //Initial state of the dp
    //dp[0][0] will be 1 if the current
    //bit is 1 and we have to flip it
    dp[0][0] = (a[0] == '1');
 
    //Initial state of the dp
    //dp[0][1] will be 1 if the current
    //bit is 0 and we have to flip it
    dp[0][1] = (a[0] == '0');
 
 
    for (int i = 1; i < n; i++)
    {
        //dp[i][0] = Flips required to
        //make all previous bits zero
        //+ Flip required to make current bit zero
        dp[i][0] = dp[i - 1][0] + (a[i] == '1');
 
 
        //dp[i][1] = minimum flips required
        //to make all previous states 0 or make
        //previous states 1 satisfying the condition
        dp[i][1] = min(dp[i - 1][0],
                       dp[i - 1][1]) + (a[i] == '0');
 
    }
    int answer = INT_MAX;
    for (int i=0;i<n;i++)
    {
        answer = min(answer, dp[i][1] +
                             dp[n - 1][0] - dp[i][0]);
     }
 
    //Minimum of answer and flips
    //required to make all bits 0
    return min(answer, dp[n - 1][0]);
}
 
//Driver Code
int main()
{
  string s = "1100111000101";
  cout<<(minFlip(s));
}
 
// This code is contributed by Mohit kumar 29

// Java implementation for
// Minimum number of flips
// required in a binary string
// such that all the 1’s are together
import java.io.*;
import java.util.*;
class GFG{
     
static int minFlip(String a)
{
  // Length of the binary string
  int n = a.length();
 
  int dp[][] = new int[n + 1][2];
 
  // Initial state of the dp
  // dp[0][0] will be 1 if
  // the current bit is 1
  // and we have to flip it
  if(a.charAt(0) == '1')
  {
    dp[0][0] = 1 ;
  }
  else dp[0][0] = 0;
 
  // Initial state of the dp
  // dp[0][1] will be 1 if
  // the current bit is 0
  // and we have to flip it
  if(a.charAt(0) == '0')
    dp[0][1] = 1;
  else dp[0][1] = 0;
 
  for (int i = 1; i < n; i++)
  {
    // dp[i][0] = Flips required to
    // make all previous bits zero
    // Flip required to make current
    // bit zero
    if(a.charAt(i) == '1')
    {
      dp[i][0] = dp[i - 1][0] + 1;
    }
    else dp[i][0] = dp[i - 1][0];
 
    // dp[i][1] = minimum flips
    // required to make all previous
    // states 0 or make previous states
    // 1 satisfying the condition
    if(a.charAt(i) == '0')
    {
      dp[i][1] = Math.min(dp[i - 1][0],
                          dp[i - 1][1]) + 1;
    }
    else dp[i][1] = Math.min(dp[i - 1][0],
                             dp[i - 1][1]);
  }
 
  int answer = Integer.MAX_VALUE;
  for (int i = 0; i < n; i++)
  {
    answer = Math.min(answer, dp[i][1] +
                      dp[n - 1][0] -
                      dp[i][0]);
  }
 
  //Minimum of answer and flips
  //required to make all bits 0
  return Math.min(answer,
                  dp[n - 1][0]);
}
   
// Driver code
public static void main (String[] args)
{
  String s = "1100111000101";
  System.out.println(minFlip(s));
}
}
 
// This code is contributed by satvikshrivas26

# Python implementation for Minimum number of
# flips required in a binary string such
# that all the 1’s are together
 
def minFlip(a):
     
     # Length of the binary string
    n = len(a)
     
    dp =[[0, 0] for i in range(n)]
     
    # Initial state of the dp
    # dp[0][0] will be 1 if the current
    # bit is 1 and we have to flip it
    dp[0][0]= int(a[0]=='1')
     
    # Initial state of the dp
    # dp[0][1] will be 1 if the current
    # bit is 0 and we have to flip it
    dp[0][1]= int(a[0]=='0')
     
 
    for i in range(1, n):
         
         
        # dp[i][0] = Flips required to
        # make all previous bits zero
        # + Flip required to make current bit zero
        dp[i][0]= dp[i-1][0]+int(a[i]=='1')
         
         
        # dp[i][1] = minimum flips required
        # to make all previous states 0 or make
        # previous states 1 satisfying the condition
        dp[i][1]= min(dp[i-1])+int(a[i]=='0')
         
     
 
    answer = 10**18
     
    for i in range(n):
        answer = min(answer,
                     dp[i][1]+dp[n-1][0]-dp[i][0])
     
    # Minimum of answer and flips
    # required to make all bits 0
    return min(answer, dp[n-1][0])
     
 
# Driver code
s = "1100111000101"
 
print(minFlip(s))

// C# implementation for
// Minimum number of
// flips required in
// a binary string such
// that all the 1’s are together
using System;
class GFG{
  
static int minFlip(string a)
{
  //Length of the binary string
  int n = a.Length;
 
  int [,]dp=new int[n + 1, 2];
 
  //Initial state of the dp
  //dp[0][0] will be 1 if the current
  //bit is 1 and we have to flip it
  dp[0, 0] = (a[0] == '1' ? 1 : 0);
 
  //Initial state of the dp
  //dp[0][1] will be 1 if the current
  //bit is 0 and we have to flip it
  dp[0, 1] = (a[0] == '0' ? 1 : 0);
 
  for (int i = 1; i < n; i++)
  {
    //dp[i][0] = Flips required to
    //make all previous bits zero
    //+ Flip required to make current bit zero
    dp[i, 0] = dp[i - 1, 0] +
                 (a[i] == '1' ? 1 : 0);
 
    //dp[i][1] = minimum flips required
    //to make all previous states 0 or make
    //previous states 1 satisfying the condition
    dp[i, 1] = Math.Min(dp[i - 1, 0],
                        dp[i - 1, 1]) +
                       (a[i] == '0' ? 1 : 0);
 
  }
  int answer = int.MaxValue;
   
  for (int i = 0; i < n; i++)
  {
    answer = Math.Min(answer, dp[i, 1] +
                      dp[n - 1, 0] - dp[i, 0]);
  }
 
  //Minimum of answer and flips
  //required to make all bits 0
  return Math.Min(answer, dp[n - 1, 0]);
}
  
// Driver code
public static void Main(string[] args)
{
  string s = "1100111000101";
  Console.Write(minFlip(s));
}
}
 
// This code is contributed by Rutvik_56

<script>
// Javascript implementation for
// Minimum number of flips
// required in a binary string
// such that all the 1’s are together
function minFlip(a)
{
 
    // Length of the binary string
    let n = a.length;
    let dp = new Array(n + 2).fill(0).map((t) => new Array(2).fill(0))
 
    // Initial state of the dp
    // dp[0][0] will be 1 if
    // the current bit is 1
    // and we have to flip it
    if (a.charAt(0) == '1') {
        dp[0][0] = 1;
    }
    else dp[0][0] = 0;
 
    // Initial state of the dp
    // dp[0][1] will be 1 if
    // the current bit is 0
    // and we have to flip it
    if (a.charAt(0) == '0')
        dp[0][1] = 1;
    else dp[0][1] = 0;
 
    for (let i = 1; i < n; i++)
    {
     
        // dp[i][0] = Flips required to
        // make all previous bits zero
        // Flip required to make current
        // bit zero
        if (a.charAt(i) == '1') {
            dp[i][0] = dp[i - 1][0] + 1;
        }
        else dp[i][0] = dp[i - 1][0];
 
        // dp[i][1] = minimum flips
        // required to make all previous
        // states 0 or make previous states
        // 1 satisfying the condition
        if (a.charAt(i) == '0') {
            dp[i][1] = Math.min(dp[i - 1][0],
                dp[i - 1][1]) + 1;
        }
        else dp[i][1] = Math.min(dp[i - 1][0],
            dp[i - 1][1]);
    }
 
    let answer = Number.MAX_SAFE_INTEGER;
    for (let i = 0; i < n; i++) {
        answer = Math.min(answer, dp[i][1] +
            dp[n - 1][0] -
            dp[i][0]);
    }
 
    // Minimum of answer and flips
    // required to make all bits 0
    return Math.min(answer,
        dp[n - 1][0]);
}
 
// Driver code
let s = "1100111000101";
document.write(minFlip(s));
 
// This code is contributed by _saurabh_jaiswal.
</script>

4

Complejidad de tiempo: O(N)

Espacio auxiliar: O(N), donde N es la longitud de la string.