Eliminación mínima de caracteres similares consecutivos necesarios para vaciar una string binaria

Dada una string binaria S de longitud N , la tarea es encontrar el número mínimo de eliminación de caracteres adyacentes similares necesarios para vaciar la string binaria dada .

Ejemplos:

Entrada: S = «1100011»
Salida: 2
Explicación:
Operación 1: La eliminación de todos los 0 modifica S a «1111».
Operación 2: La eliminación de todos los 1 restantes hace que S quede vacío.
Por lo tanto, el número mínimo de operaciones requeridas es 2.

Entrada: S = “0010100“
Salida: 3
Explicación:
Operación 1: La eliminación de todos los 1 modifica S a “000100“.
Operación 2: La eliminación de todos los 1 modifica S = «00000».
Operación 3: La eliminación de todos los 0 restantes hace que S quede vacío.
Por lo tanto, el número mínimo de operaciones requeridas es de 3.

Enfoque: el problema dado se puede resolver utilizando el enfoque codicioso . La idea es eliminar las apariciones consecutivas del personaje con mayor frecuencia. Siga los pasos a continuación para resolver el problema:

• Atraviese la string S dada y genere una nueva string, digamos newString , eliminando las ocurrencias consecutivas del carácter con mayor frecuencia.
• Finalmente, imprime (sizeof(newString) + 1)/2 como la respuesta requerida

Explicación : la string dada, por ejemplo: «1100011» cambia 101 ya que estamos saltando la ocurrencia múltiple. Después de esto, devolvemos (sizeof(newString) + 1)/2 el tamaño de la nueva string es  3, 101 -> primero eliminamos el 0, lo que nos lleva 1 operación, luego la nueva string es 11  , luego hacemos solo 1 operación más para eliminar la string 11, tomando un total de 2 operaciones.

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 steps
// to make the string empty
int minSteps(string S)
{
    // Stores the modified string
    string new_str;
 
    // Size of string
    int N = S.length();
 
    int i = 0;
 
    while (i < N) {
 
        new_str += S[i];
 
        // Removing substring of same
        // character from modified string
        int j = i;
        while (i < N && S[i] == S[j])
            ++i;
    }
 
    // Print the minimum steps required
    cout << ceil((new_str.size() + 1) / 2.0);
}
 
// Driver Code
int main()
{
    // Given string S
    string S = "0010100";
 
    // Function Call
    minSteps(S);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to find minimum steps
// to make the String empty
static void minSteps(String S)
{
     
    // Stores the modified String
    String new_str = "";
 
    // Size of String
    int N = S.length();
 
    int i = 0;
 
    while (i < N)
    {
        new_str += S.charAt(i);
         
        // Removing subString of same
        // character from modified String
        int j = i;
        while (i < N && S.charAt(i) == S.charAt(j))
            ++i;
    }
 
    // Print the minimum steps required
    System.out.print((int)Math.ceil(
        (new_str.length() + 1) / 2.0));
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given String S
    String S = "0010100";
 
    // Function Call
    minSteps(S);
}
}
 
// This code is contributed by Princi Singh

# Python3 program for the above approach
from math import ceil
 
# Function to find minimum steps
# to make the empty
def minSteps(S):
     
    # Stores the modified string
    new_str = ""
 
    # Size of string
    N = len(S)
 
    i = 0
 
    while (i < N):
        new_str += S[i]
 
        # Removing substring of same character
        # from modified string
        j = i
        while (i < N and S[i] == S[j]):
            i += 1
 
    # Print the minimum steps required
    print(ceil((len(new_str) + 1) / 2))
 
# Driver Code
if __name__ == '__main__':
     
    # Given S
    S = "0010100"
 
    # Function Call
    minSteps(S)
 
# This code is contributed by mohit kumar 29

// C# program for the above approach
using System;
 
class GFG{
 
// Function to find minimum steps
// to make the string empty
static void minSteps(string S)
{
     
    // Stores the modified string
    string new_str = "";
     
    // Size of string
    int N = S.Length;
 
    int i = 0;
 
    while (i < N)
    {
        new_str += S[i];
         
        // Removing substring of same
        // character from modified string
        int j = i;
         
        while (i < N && S[i] == S[j])
            ++i;
    }
 
    // Print the minimum steps required
    Console.Write((int)Math.Ceiling(
        (new_str.Length + 1) / 2.0));
}
 
// Driver Code
public static void Main()
{
     
    // Given string S
    string S = "0010100";
 
    // Function Call
    minSteps(S);
}
}
 
// This code is contributed by SURENDRA_GANGWAR

<script>
// Javascript program to implement
// the above approach
 
// Function to find minimum steps
// to make the string empty
function minSteps(S)
{
      
    // Stores the modified string
    let new_str = "";
      
    // Size of string
    let N = S.length;
  
    let i = 0;
  
    while (i < N)
    {
        new_str += S[i];
          
        // Removing substring of same
        // character from modified string
        let j = i;
          
        while (i < N && S[i] == S[j])
            ++i;
    }
  
    // Print the minimum steps required
    document.write(Math.ceil(
        (new_str.length + 1) / 2.0));
}
 
    // Driver Code
     
    // Given string S
    let S = "0010100";
  
    // Function Call
    minSteps(S)
      
</script>

3

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