Maximice la cantidad de veces que se puede eliminar un carácter de la substring 01 de una string binaria dada

Dada una string binaria S de tamaño N , la tarea es encontrar el número máximo de operaciones que se pueden realizar en S , seleccionando cualquier substring » 01 » y eliminando cualquier carácter de ella en un solo movimiento, reduciendo la longitud de la string. por 1 .

Ejemplos:

Entrada: S = “001111”, N = 6
Salida: 5
Explicación: 
Una forma de realizar las operaciones es:

1. Seleccione la substring “01” sobre el rango [1, 2] y borre la S[2] (= ‘1’). La string se modifica a «00111».
2. Seleccione la substring “01” sobre el rango [1, 2] y borre la S[2] (= ‘1’). La string se modifica a «0011».
3. Seleccione la substring “01” sobre el rango [1, 2] y borre la S[2] (= ‘1’). La string se modifica a «001».
4. Seleccione la substring “01” sobre el rango [1, 2] y borre la S[1] (= ‘0’). La string se modifica a «01».
5. Seleccione la substring “01” sobre el rango [0, 1] y borre la S[1] (= ‘1’). La string se modifica a «0».
6. Ahora no se pueden eliminar caracteres.

Por tanto, el número total de operaciones realizadas es de 5, que es el máximo posible.

Entrada: S=”0101″, N=4
Salida: 3

Enfoque: El problema dado se puede resolver con base en las siguientes observaciones: 

1. Los 1 presentes en el prefijo de S no se pueden eliminar porque no hay 0 antes de ellos.
2. Los 0 presentes en el sufijo de S no se pueden eliminar porque no hay 1 después de ellos.
3. Todos los demás personajes son extraíbles.
4. Si hay X caracteres eliminables, como máximo se pueden realizar operaciones X-1 porque, eventualmente, solo quedará un carácter que no se puede eliminar.

Siga los pasos a continuación para resolver el problema:

• Inicialice dos variables, digamos X e Y como 0 , que almacenan la cantidad de 0 en el sufijo y la cantidad de 1 en el prefijo respectivamente, que no se pueden eliminar.
• Iterar sobre los caracteres de la string S y realizar los siguientes pasos:
  • Si el carácter actual es ‘ 1 ‘ , incremente Y en 1.
  • De lo contrario, deje de atravesar.
• Iterar sobre los caracteres de la string S en orden inverso y realizar los siguientes pasos:
  • Si el carácter actual es 0 , incremente X en 1 .
  • De lo contrario, deje de atravesar.
• Si la suma de X e Y es igual a N , imprime 0 ya que no hay caracteres removibles.
• De lo contrario, imprima N-(X+Y)-1 como respuesta.

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 the maximum moves
// that can be performed on a string
int maxOperations(string S, int N)
{
    // Stores 0s in suffix
    int X = 0;
    // Stores 1s in prefix
    int Y = 0;
 
    // Iterate over the characters of
    // the string
    for (int i = 0; i < N; i++) {
        if (S[i] == '0')
            break;
        Y++;
    }
    // Iterate until i is greater than
    // or equal to 0
    for (int i = N - 1; i >= 0; i--) {
        if (S[i] == '1')
            break;
        X++;
    }
 
    // If N is equal to x+y
    if (N == X + Y)
        return 0;
 
    // Return answer
    return N - (X + Y) - 1;
}
// Driver code
int main()
{
    // Input
    string S = "001111";
    int N = S.length();
 
    // Function call
    cout << maxOperations(S, N) << endl;
    return 0;
}

// Java program for the above approach
import java.io.*;
 
class GFG{
 
// Function to find the maximum moves
// that can be performed on a string
static int maxOperations(String S, int N)
{
     
    // Stores 0s in suffix
    int X = 0;
     
    // Stores 1s in prefix
    int Y = 0;
 
    // Iterate over the characters of
    // the string
    for(int i = 0; i < N; i++)
    {
        if (S.charAt(i) == '0')
            break;
             
        Y++;
    }
     
    // Iterate until i is greater than
    // or equal to 0
    for(int i = N - 1; i >= 0; i--)
    {
        if (S.charAt(i) == '1')
            break;
             
        X++;
    }
 
    // If N is equal to x+y
    if (N == X + Y)
        return 0;
 
    // Return answer
    return N - (X + Y) - 1;
}
 
// Driver code
public static void main(String[] args)
{
     
    // Input
    String S = "001111";
    int N = S.length();
     
    // Function call
    System.out.println(maxOperations(S, N));
}
}
 
// This code is contributed by sanjoy_62

# Python3 program for the above approach
 
# Function to find the maximum moves
# that can be performed on a string
def maxOperations(S, N):
     
    # Stores 0s in suffix
    X = 0
     
    # Stores 1s in prefix
    Y = 0
 
    # Iterate over the characters of
    # the string
    for i in range(N):
        if (S[i] == '0'):
            break
         
        Y += 1
         
    # Iterate until i is greater than
    # or equal to 0
    i = N - 1
    while(i >= 0):
        if (S[i] == '1'):
            break
         
        X += 1
 
    # If N is equal to x+y
    if (N == X + Y):
        return 0
 
    # Return answer
    return N - (X + Y) - 1
 
# Driver code
if __name__ == '__main__':
     
    # Input
    S = "001111"
    N = len(S)
 
    # Function call
    print(maxOperations(S, N))
     
# This code is contributed by SURENDRA_GANGWAR

// C# program for the above approach
using System;
 
class GFG{
     
// Function to find the maximum moves
// that can be performed on a string
static int maxOperations(String S, int N)
{
     
    // Stores 0s in suffix
    int X = 0;
 
    // Stores 1s in prefix
    int Y = 0;
 
    // Iterate over the characters of
    // the string
    for(int i = 0; i < N; i++)
    {
        if (S[i] == '0')
            break;
 
        Y++;
    }
 
    // Iterate until i is greater than
    // or equal to 0
    for(int i = N - 1; i >= 0; i--)
    {
        if (S[i] == '1')
            break;
 
        X++;
    }
 
    // If N is equal to x+y
    if (N == X + Y)
        return 0;
 
    // Return answer
    return N - (X + Y) - 1;
}
 
// Driver code
static void Main()
{
     
    // Input
    String S = "001111";
    int N = S.Length;
 
    // Function call
    Console.WriteLine(maxOperations(S, N));
}
}
 
// This code is contributed by abhinavjain194

<script>
 
// JavaScript program for the above approach
 
// Function to find the maximum moves
// that can be performed on a string
function maxOperations(S, N)
{
     
    // Stores 0s in suffix
    let X = 0;
 
    // Stores 1s in prefix
    let Y = 0;
 
    // Iterate over the characters of
    // the string
    for(let i = 0; i < N; i++)
    {
        if (S[i] == '0')
            break;
 
        Y++;
    }
 
    // Iterate until i is greater than
    // or equal to 0
    for(let i = N - 1; i >= 0; i--)
    {
        if (S[i] == '1')
            break;
 
        X++;
    }
 
    // If N is equal to x+y
    if (N == X + Y)
        return 0;
 
    // Return answer
    return N - (X + Y) - 1;
}
             
 
// Driver Code
 
    // Input
    let S = "001111";
    let N = S.length;
     
    // Function call
    document.write(maxOperations(S, N));
 
</script>

5

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