Imprimir string después de eliminar todo («10» o «01») de la string binaria

Posted on by Rudeus Greyrat

Dada una string binaria str que consta solo de 0 y 1, la tarea es imprimir la string después de eliminar las ocurrencias de «10» y «01» de la string una por una. Imprime -1 si la string se vuelve nula. 

Ejemplos: 

Entrada: str = «101100» 
Salida: -1 
Explicación: 
En el primer paso, «10» en el índice 0 y 1 se elimina de la string. 
101100 -> 1100 
En el segundo paso, «10» en el índice 1 y 2 se elimina de la string. 
1100 -> 10 
Finalmente, se elimina «10» y la string queda vacía. 
10 -> NULO

Entrada: str = “010110100” 
Salida: 0 
Explicación: 
En el primer paso, “01” en el índice 0 y 1 se elimina de la string. 
010110100 -> 0110100 
En el segundo paso, «01» en el índice 0 y 1 se elimina de la string. 
0110100 -> 10100 
En el tercer paso, «10» en el índice 0 y 1 se elimina de la string. 
10100 -> 100 
Finalmente, se elimina «10» y la string se convierte en «0». 
100 -> 0

Observación: al observar con atención, dado que la string dada es una string binaria, todas las strings se pueden borrar excepto los 0 y 1 adicionales que están presentes en la string que no se pueden emparejar con su complemento. Por ejemplo:  

Sea str = “010110100”. 
Para esta string, la cantidad de 0 es 5 y la cantidad de 1 es 4. 
Ahora, comencemos a eliminar las substrings alternativas una por una: 

  1. 01 0110100 -> 0110100
  2. 01 10100 -> 10100
  3. 10 100 -> 100
  4. 10 0 -> 0

En este punto, la string no se puede reducir más. 
 

Por lo tanto, a partir del ejemplo anterior, se puede visualizar que la string se puede reducir siempre que haya 1 y 0 en la string. 
Ya discutimos el enfoque para encontrar el conteo de eliminaciones de 0 y 1 en el artículo anterior . Aquí, hemos realizado una ligera modificación en el enfoque anterior para generar la string restante después de todas las eliminaciones posibles.

Enfoque: A partir de la observación anterior, se puede concluir que las strings finales contienen solo los 1 o 0 adicionales que no se pueden emparejar con ninguno de los dígitos de la string. Por lo tanto, la idea para resolver este problema es contar la cantidad de 0 y 1 en la string y encontrar la diferencia entre las dos cuentas. Este conteo significa el número de 1 o 0 restantes según el valor que sea mayor. 

Se pueden seguir los siguientes pasos para calcular la respuesta:  

  1. Obtenga el recuento de 0 presentes en la string y guárdelo en una variable.
  2. Obtenga el conteo de 1 presentes en la string y guárdelo en otra variable.
  3. Si el conteo de 1 es igual a 0 , entonces se puede reducir toda la string. Por lo tanto, devuelve -1 .
  4. Si el conteo de 1 es mayor que el conteo de 0 , entonces finalmente esos muchos 1 se quedan y no sería posible una mayor reducción. Por lo tanto, agregue esos muchos 1 a una string vacía y devuelva la string.
  5. De manera similar, si el conteo de 0 es mayor que el conteo de 1 , encuentre la diferencia y agregue esos muchos 0 a una string vacía y devuélvalo.

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

C++

// C++ program to print the final string
// after removing all the occurrences of
// "10" and "01" from the given binary string
#include <bits/stdc++.h>
using namespace std;
 
// Function to print the final string
// after removing all the occurrences of
// "10" and "01" from the given binary string
void finalString(string str)
{
 
    // Variables to store the
    // count of 1's and 0's
    int x = 0, y = 0;
 
    // Variable left will store
    // whether 0's or 1's is left
    // in the final string
    int left;
 
    // Length of the string
    int n = str.length();
 
    // For loop to count the occurrences
    // of 1's and 0's in the string
    for (int i = 0; i < n; i++) {
        if (str[i] == '1')
            x++;
        else
            y++;
    }
 
    // To check if the count of 1's is
    // greater than the count of 0's or not.
    // If x is greater, then those many 1's
    // are printed.
    if (x > y)
        left = 1;
    else
        left = 0;
 
    // Length of the final remaining string
    // after removing all the occurrences
    int length = n - 2 * min(x, y);
 
    // Printing the final string
    for (int i = 0; i < length; i++) {
        cout << left;
    }
}
 
// Driver Code
int main()
{
    string str = "010110100100000";
    finalString(str);
 
    return 0;
}

Java

// Java program to print the final String
// after removing all the occurrences of
// "10" and "01" from the given binary String
import java.util.*;
 
class GFG{
  
// Function to print the final String
// after removing all the occurrences of
// "10" and "01" from the given binary String
static void finalString(String str)
{
  
    // Variables to store the
    // count of 1's and 0's
    int x = 0, y = 0;
  
    // Variable left will store
    // whether 0's or 1's is left
    // in the final String
    int left;
  
    // Length of the String
    int n = str.length();
  
    // For loop to count the occurrences
    // of 1's and 0's in the String
    for (int i = 0; i < n; i++) {
        if (str.charAt(i) == '1')
            x++;
        else
            y++;
    }
  
    // To check if the count of 1's is
    // greater than the count of 0's or not.
    // If x is greater, then those many 1's
    // are printed.
    if (x > y)
        left = 1;
    else
        left = 0;
  
    // Length of the final remaining String
    // after removing all the occurrences
    int length = n - 2 * Math.min(x, y);
  
    // Printing the final String
    for (int i = 0; i < length; i++) {
        System.out.print(left);
    }
}
  
// Driver Code
public static void main(String[] args)
{
    String str = "010110100100000";
    finalString(str);
}
}
 
// This code is contributed by sapnasingh4991

Python3

# Python 3 program to print the final string
# after removing all the occurrences of
# "10" and "01" from the given binary string
 
# Function to print the final string
# after removing all the occurrences of
# "10" and "01" from the given binary string
def finalString(st):
 
    # Variables to store the
    # count of 1's and 0's
    x , y = 0 , 0
 
    # Length of the string
    n = len(st)
 
    # For loop to count the occurrences
    # of 1's and 0's in the string
    for i in range( n):
        if (st[i] == '1'):
            x += 1
        else:
            y += 1
 
    # To check if the count of 1's is
    # greater than the count of 0's or not.
    # If x is greater, then those many 1's
    # are printed.
    if (x > y):
        left = 1
    else:
        left = 0
 
    # Length of the final remaining string
    # after removing all the occurrences
    length = n - 2 * min(x, y);
 
    # Printing the final string
    for i in range(length):
        print(left, end="")
 
 
# Driver Code
if __name__ == "__main__":
    st = "010110100100000"
    finalString(st)
 
# This code is contributed by chitranayal
    

C#

// C# program to print the readonly String
// after removing all the occurrences of
// "10" and "01" from the given binary String
using System;
 
class GFG{
   
// Function to print the readonly String
// after removing all the occurrences of
// "10" and "01" from the given binary String
static void finalString(String str)
{
   
    // Variables to store the
    // count of 1's and 0's
    int x = 0, y = 0;
   
    // Variable left will store
    // whether 0's or 1's is left
    // in the readonly String
    int left;
   
    // Length of the String
    int n = str.Length;
   
    // For loop to count the occurrences
    // of 1's and 0's in the String
    for (int i = 0; i < n; i++) {
        if (str[i] == '1')
            x++;
        else
            y++;
    }
   
    // To check if the count of 1's is
    // greater than the count of 0's or not.
    // If x is greater, then those many 1's
    // are printed.
    if (x > y)
        left = 1;
    else
        left = 0;
   
    // Length of the readonly remaining String
    // after removing all the occurrences
    int length = n - 2 * Math.Min(x, y);
   
    // Printing the readonly String
    for (int i = 0; i < length; i++) {
        Console.Write(left);
    }
}
   
// Driver Code
public static void Main(String[] args)
{
    String str = "010110100100000";
    finalString(str);
}
}
  
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// Javascript program to print the final String
// after removing all the occurrences of
// "10" and "01" from the given binary String
 
// Function to print the final String
// after removing all the occurrences of
// "10" and "01" from the given binary String
function finalString(str)
{
    
    // Variables to store the
    // count of 1's and 0's
    let x = 0, y = 0;
    
    // Variable left will store
    // whether 0's or 1's is left
    // in the final String
    let left;
    
    // Length of the String
    let n = str.length;
    
    // For loop to count the occurrences
    // of 1's and 0's in the String
    for (let i = 0; i < n; i++) {
        if (str[i] == '1')
            x++;
        else
            y++;
    }
    
    // To check if the count of 1's is
    // greater than the count of 0's or not.
    // If x is greater, then those many 1's
    // are printed.
    if (x > y)
        left = 1;
    else
        left = 0;
    
    // Length of the final remaining String
    // after removing all the occurrences
    let length = n - 2 * Math.min(x, y);
    
    // Printing the final String
    for (let i = 0; i < length; i++) {
        document.write(left);
    }
}
 
// Driver Code
 
    let  str = "010110100100000";
    finalString(str);
 
</script>
Producción: 

00000

 

Análisis de Complejidad de Tiempo:

  • El ciclo for para contar las ocurrencias de 1 y 0 toma el tiempo O(N) donde N es la longitud de la string.
  • La instrucción if toma un tiempo constante. Entonces, la complejidad de tiempo para la declaración if es O(1) .
  • El ciclo para imprimir la string final toma O(N) en el peor de los casos cuando toda la string es solo 0 o 1.
  • Por lo tanto, la complejidad temporal total es O(N) .

Publicación traducida automáticamente

Artículo escrito por skylags y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *