Minimice la eliminación de subsecuencias alternas para vaciar la string binaria dada

Dada una string binaria S de longitud N , la tarea es minimizar el recuento de eliminación repetitiva de la subsecuencia alterna del 0 y el 1 de la string binaria S dada para hacer que la string quede vacía .

Ejemplos:

Entrada: S = “0100100111”
Salida: 3
Explicación: 
Quitar la subsecuencia “010101” de S para modificarla a “0011”. 
Elimine «01» de «0011» para convertirlo en «01». 
Finalmente, elimine «01» para convertirlo en una string vacía.

Entrada: S = “1111”
Salida: 4

Enfoque: el problema dado se puede resolver observando que se debe eliminar una subsecuencia alterna de 0 y 1 y que para eliminar todos los caracteres consecutivos, los 1 o 0 solo se pueden eliminar en cada operación por separado, no en una sola operación.

Por lo tanto, el número mínimo de operaciones requeridas es el número máximo de 0 y 1 consecutivos .

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

#include <iostream>
using namespace std;
 
void minOpsToEmptyString(string S, int N)
{
    // Initialize variables
    int one = 0, zero = 0;
 
    int x0 = 0, x1 = 0;
 
    // Traverse the string
    for (int i = 0; i < N; i++) {
 
        // If current character is 0
        if (S[i] == '0') {
            x0++;
            x1 = 0;
        }
        else {
            x1++;
            x0 = 0;
        }
 
        // Update maximum consecutive
        // 0s and 1s
        zero = max(x0, zero);
        one = max(x1, one);
    }
 
    // Print the minimum operation
    cout << max(one, zero) << endl;
}
 
// Driver code+
int main()
{
   
    // input string
    string S = "0100100111";
   
    // length of string
    int N = S.length();
   
    // Function Call
    minOpsToEmptyString(S, N);
}
 
// This code is contributed by aditya7409

// Java program for the above approach
 
import java.io.*;
import java.util.*;
 
class GFG {
 
    // Function to find the minimum
    // number of operations required
    // to empty the string
    public static void
    minOpsToEmptyString(String S,
                        int N)
    {
        // Initialize variables
        int one = 0, zero = 0;
 
        int x0 = 0, x1 = 0;
 
        // Traverse the string
        for (int i = 0; i < N; i++) {
 
            // If current character is 0
            if (S.charAt(i) == '0') {
                x0++;
                x1 = 0;
            }
            else {
                x1++;
                x0 = 0;
            }
 
            // Update maximum consecutive
            // 0s and 1s
            zero = Math.max(x0, zero);
            one = Math.max(x1, one);
        }
 
        // Print the minimum operation
        System.out.println(
            Math.max(one, zero));
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        String S = "0100100111";
        int N = S.length();
 
        // Function Call
        minOpsToEmptyString(S, N);
    }
}

# Python3 program for the above approach
def minOpsToEmptyString(S, N):
 
    # Initialize variables
    one = 0
    zero = 0
    x0 = 0
    x1 = 0
 
    # Traverse the string
    for i in range(N):
 
        # If current character is 0
        if (S[i] == '0'):
            x0 += 1
            x1 = 0
        else:
            x1 += 1
            x0 = 0
 
        # Update maximum consecutive
        # 0s and 1s
        zero = max(x0, zero)
        one = max(x1, one)
 
    # Print the minimum operation
    print(max(one, zero))
 
# Driver code+
if __name__ == "__main__":
 
    # input string
    S = "0100100111"
 
    # length of string
    N = len(S)
 
    # Function Call
    minOpsToEmptyString(S, N)
 
    # This code is contributed by chitranayal

// C# program for the above approach
using System;
class GFG
{
 
    // Function to find the minimum
    // number of operations required
    // to empty the string
    public static void
      minOpsToEmptyString(string S, int N)
    {
        // Initialize variables
        int one = 0, zero = 0;
 
        int x0 = 0, x1 = 0;
 
        // Traverse the string
        for (int i = 0; i < N; i++)
        {
 
            // If current character is 0
            if (S[i] == '0')
            {
                x0++;
                x1 = 0;
            }
            else
            {
                x1++;
                x0 = 0;
            }
 
            // Update maximum consecutive
            // 0s and 1s
            zero = Math.Max(x0, zero);
            one = Math.Max(x1, one);
        }
 
        // Print the minimum operation
        Console.WriteLine(Math.Max(one, zero));
    }
 
    // Driver Code
    static public void Main()
    {
        string S = "0100100111";
        int N = S.Length;
 
        // Function Call
        minOpsToEmptyString(S, N);
    }
}
 
// This code is contributed by Dharanendra L V

<script>
 
// Javascript program of the above approach
 
// Function to find the minimum
// number of operations required
// to empty the string
function minOpsToEmptyString(S, N)
{
     
    // Initialize variables
    let one = 0, zero = 0;
 
    let x0 = 0, x1 = 0;
 
    // Traverse the string
    for(let i = 0; i < N; i++)
    {
         
        // If current character is 0
        if (S[i] == '0')
        {
            x0++;
            x1 = 0;
        }
        else
        {
            x1++;
            x0 = 0;
        }
 
        // Update maximum consecutive
        // 0s and 1s
        zero = Math.max(x0, zero);
        one = Math.max(x1, one);
    }
 
    // Print the minimum operation
    document.write(Math.max(one, zero));
}
 
// Driver Code
let S = "0100100111";
let N = S.length;
 
// Function Call
minOpsToEmptyString(S, N);
 
// This code is contributed by chinmoy1997pal
 
</script>

3

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