Minimice los giros requeridos de modo que la string no tenga ningún par de 0 consecutivos

Dada una string binaria S , la tarea es encontrar el número mínimo de vueltas necesarias para modificar una string de modo que no contenga ningún par de 0 consecutivos .

Ejemplos:

Entrada: S = “10001”
Salida: 1
Explicación: 
Voltear S[2] modifica S a “10101”. 
Por lo tanto, la salida requerida es 1.

Entrada: S = “100001”
Salida: 2
Explicación: 
Voltear S[1] modifica S a “110001”. 
Voltear S[3] modifica S a «110101».

Enfoque: El problema se puede resolver usando la técnica Greedy . Siga los pasos a continuación para resolver el problema:

• Iterar sobre los caracteres de la string . Para cada i- ^ésimo carácter, compruebe si S[i] y S[i + 1] son ​​iguales a ‘0’ o no. Si se encuentra que es cierto, entonces incremente el conteo y actualice S[i + 1] a ‘1’ .
• Finalmente, imprima el conteo obtenido.

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find minimum flips required
// such that a string does not contain
// any pair of consecutive 0s
bool cntMinOperation(string S, int N)
{
 
    // Stores minimum count of flips
    int cntOp = 0;
 
    // Iterate over the characters
    // of the string
    for (int i = 0; i < N - 1; i++) {
 
        // If two consecutive characters
        // are equal to '0'
        if (S[i] == '0' && S[i + 1] == '0') {
 
            // Update S[i + 1]
            S[i + 1] = '1';
 
            // Update cntOp
            cntOp += 1;
        }
    }
 
    return cntOp;
}
 
// Driver Code
int main()
{
    string S = "10001";
    int N = S.length();
    cout << cntMinOperation(S, N);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
class GFG
{
 
// Function to find minimum flips required
// such that a String does not contain
// any pair of consecutive 0s
static int cntMinOperation(char []S, int N)
{
 
    // Stores minimum count of flips
    int cntOp = 0;
 
    // Iterate over the characters
    // of the String
    for (int i = 0; i < N - 1; i++)
    {
 
        // If two consecutive characters
        // are equal to '0'
        if (S[i] == '0' && S[i + 1] == '0')
        {
 
            // Update S[i + 1]
            S[i + 1] = '1';
 
            // Update cntOp
            cntOp += 1;
        }
    }
    return cntOp;
}
 
// Driver Code
public static void main(String[] args)
{
    String S = "10001";
    int N = S.length();
    System.out.print(cntMinOperation(S.toCharArray(), N));
}
}
 
// This code is contributed by shikhasingrajput

# Python3 program for the above approach
 
# Function to find minimum flips required
# such that a string does not contain
# any pair of consecutive 0s
def cntMinOperation(S, N):
 
    # Stores minimum count of flips
    cntOp = 0
 
    # Iterate over the characters
    # of the string
    for i in range(N - 1):
 
        # If two consecutive characters
        # are equal to '0'
        if (S[i] == '0' and S[i + 1] == '0'):
 
            # Update S[i + 1]
            S[i + 1] = '1'
 
            # Update cntOp
            cntOp += 1
    return cntOp
 
# Driver Code
if __name__ == '__main__':
    S = "10001"
    N = len(S)
    print(cntMinOperation([i for i in S], N))
 
# This code is contributed by mohit kumar 29.

// C# program for the above approach
using System;
class GFG
{
 
  // Function to find minimum flips required
  // such that a String does not contain
  // any pair of consecutive 0s
  static int cntMinOperation(char []S, int N)
  {
 
    // Stores minimum count of flips
    int cntOp = 0;
 
    // Iterate over the characters
    // of the String
    for (int i = 0; i < N - 1; i++)
    {
 
      // If two consecutive characters
      // are equal to '0'
      if (S[i] == '0' && S[i + 1] == '0')
      {
 
        // Update S[i + 1]
        S[i + 1] = '1';
 
        // Update cntOp
        cntOp += 1;
      }
    }
    return cntOp;
  }
 
  // Driver Code
  public static void Main(string[] args)
  {
    string S = "10001";
    int N = S.Length;
    Console.WriteLine(cntMinOperation(S.ToCharArray(), N));
  }
}
 
// This code is contributed by AnkThon

<script>
 
    // JavaScript program for the above approach
     
    // Function to find minimum flips required
    // such that a String does not contain
    // any pair of consecutive 0s
    function cntMinOperation(S, N)
    {
 
      // Stores minimum count of flips
      let cntOp = 0;
 
      // Iterate over the characters
      // of the String
      for (let i = 0; i < N - 1; i++)
      {
 
        // If two consecutive characters
        // are equal to '0'
        if (S[i] == '0' && S[i + 1] == '0')
        {
 
          // Update S[i + 1]
          S[i + 1] = '1';
 
          // Update cntOp
          cntOp += 1;
        }
      }
      return cntOp;
    }
     
    let S = "10001";
    let N = S.length;
    document.write(cntMinOperation(S.split(''), N));
 
</script>

1

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