Encuentre el último carácter restante en la string binaria de acuerdo con las condiciones dadas

Dada una string binaria str que consta solo de 0 y 1. En él se pueden realizar las dos operaciones siguientes: 
 

1. Un dígito puede borrar otro dígito, es decir, un 0 puede borrar un 1 y viceversa.
2. Si en algún momento, la string completa consta solo de 0 o 1, entonces se imprime el dígito respectivo.

La tarea es imprimir el dígito restante que quedará al final.
Ejemplos: 
 

Entrada: str = “100” 
Salida: 0 
Explicación: 
El primer dígito es 1 y borra el siguiente dígito 0. 
El segundo dígito, es decir, 0, se borra y ahora no existe. 
Ahora, el tercer dígito 0 borra el primer dígito 1. 
Como ahora solo queda 0, la salida es 0.
Entrada: str = «10» 
Salida: 1 
 

Enfoque: para esta cola se utiliza la estructura de datos. Se pueden seguir los siguientes pasos para calcular la respuesta: 
 

1. Todos los dígitos se agregan a la cola.
2. Se mantienen dos contadores como una array de tamaño 2 del[2] que representará el número de eliminaciones flotantes presentes para cada dígito.
3. La cola se recorre hasta que sale al menos un dígito de ambos tipos.
4. Luego, para cada dígito en la cola, si el contador de eliminación para este dígito no es 0, entonces se elimina.
5. De lo contrario, el contador de eliminación para el dígito opuesto se incrementa y se vuelve a colocar en la cola.

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

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
 
string remainingDigit(string S, int N)
{
     
 
    // Delete counters for each to
    // count the deletes
    int del[] = { 0, 0 };
 
    // Counters to keep track
    // of characters left from each type
    int count[] = { 0, 0 };
 
    // Queue to simulate the process
    queue<int> q;
 
    // Initializing the queue
    for (int i = 0; i < N; i++)
    {
        int x = S[i] == '1' ? 1 : 0;
        count[x]++;
        q.push(x);
    }
 
    // Looping till at least 1 digit is
    // left from both the type
    while (count[0] > 0 && count[1] > 0)
    {
        int t = q.front();
        q.pop();
 
        // If there is a floating delete for
        // current character we will
        // delete it and move forward otherwise
        // we will increase delete counter for
        // opposite digit
        if (del[t] > 0)
        {
            del[t]--;
            count[t]--;
        }
        else
        {
            del[t ^ 1]++;
            q.push(t);
        }
    }
 
    // If 0 are left
    // then answer is 0 else
    // answer is 1
    if (count[0] > 0)
        return "0";
    return "1";
}
 
// Driver Code
int main()
{
 
    // Input String
    string S = "1010100100000";
 
    // Length of String
    int N = S.length();
 
    // Printing answer
    cout << remainingDigit(S, N);
}
 
// This code is contributed by tufan_gupta2000

// Java implementation of the above approach
 
import java.util.*;
 
public class GfG {
    private static String remainingDigit(String S, int N)
    {
        // Converting string to array
        char c[] = S.toCharArray();
 
        // Delete counters for each to
        // count the deletes
        int del[] = { 0, 0 };
 
        // Counters to keep track
        // of characters left from each type
        int count[] = { 0, 0 };
 
        // Queue to simulate the process
        Queue<Integer> q = new LinkedList<>();
 
        // Initializing the queue
        for (int i = 0; i < N; i++) {
            int x = c[i] == '1' ? 1 : 0;
            count[x]++;
            q.add(x);
        }
 
        // Looping till at least 1 digit is
        // left from both the type
        while (count[0] > 0 && count[1] > 0) {
            int t = q.poll();
 
            // If there is a floating delete for
            // current character we will
            // delete it and move forward otherwise
            // we will increase delete counter for
            // opposite digit
            if (del[t] > 0) {
                del[t]--;
                count[t]--;
            }
            else {
                del[t ^ 1]++;
                q.add(t);
            }
        }
 
        // If 0 are left
        // then answer is 0 else
        // answer is 1
        if (count[0] > 0)
            return "0";
        return "1";
    }
 
    // Driver Code
    public static void main(String args[])
    {
 
        // Input String
        String S = "1010100100000";
 
        // Length of String
        int N = S.length();
 
        // Printing answer
        System.out.print(remainingDigit(S, N));
    }
}

# Python3 implementation of the above approach
from collections import deque;
 
def remainingDigit(S, N):
     
    # Converting string to array
    c = [i for i in S]
 
    # Delete counters for each to
    # count the deletes
    de = [0, 0]
 
    # Counters to keep track
    # of characters left from each type
    count = [0, 0]
 
    # Queue to simulate the process
    q = deque()
 
    # Initializing the queue
    for i in c:
        x = 0
        if i == '1':
            x = 1
        count[x] += 1
        q.append(x)
 
    # Looping till at least 1 digit is
    # left from both the type
    while (count[0] > 0 and count[1] > 0):
        t = q.popleft()
 
        # If there is a floating delete for
        # current character we will
        # delete it and move forward otherwise
        # we will increase delete counter for
        # opposite digit
        if (de[t] > 0):
            de[t] -= 1
            count[t] -= 1
        else:
            de[t ^ 1] += 1
            q.append(t)
 
    # If 0 are left
    # then answer is 0 else
    # answer is 1
    if (count[0] > 0):
        return "0"
    return "1"
 
# Driver Code
if __name__ == '__main__':
 
    # Input String
    S = "1010100100000"
 
    # Length of String
    N = len(S)
 
    # Printing answer
    print(remainingDigit(S, N))
 
# This code is contributed by mohit kumar 29

// C# implementation of the above approach
using System;
using System.Collections.Generic;
 
public class GfG
{
    private static String remainingDigit(String S, int N)
    {
        // Converting string to array
        char []c = S.ToCharArray();
 
        // Delete counters for each to
        // count the deletes
        int []del = { 0, 0 };
 
        // Counters to keep track
        // of characters left from each type
        int []count = { 0, 0 };
 
        // Queue to simulate the process
        List<int> q = new List<int>();
 
        // Initializing the queue
        for (int i = 0; i < N; i++)
        {
            int x = c[i] == '1' ? 1 : 0;
            count[x]++;
            q.Add(x);
        }
 
        // Looping till at least 1 digit is
        // left from both the type
        while (count[0] > 0 && count[1] > 0)
        {
            int t = q[0];
            q.RemoveAt(0);
 
            // If there is a floating delete for
            // current character we will
            // delete it and move forward otherwise
            // we will increase delete counter for
            // opposite digit
            if (del[t] > 0)
            {
                del[t]--;
                count[t]--;
            }
            else
            {
                del[t ^ 1]++;
                q.Add(t);
            }
        }
 
        // If 0 are left
        // then answer is 0 else
        // answer is 1
        if (count[0] > 0)
            return "0";
        return "1";
    }
 
    // Driver Code
    public static void Main(String []args)
    {
 
        // Input String
        String S = "1010100100000";
 
        // Length of String
        int N = S.Length;
 
        // Printing answer
        Console.Write(remainingDigit(S, N));
    }
}
 
// This code is contributed by Rajput-Ji

<script>
// Javascript implementation of the above approach
 
function remainingDigit(S,N)
{
     // Converting string to array
        let c = S.split("");
   
        // Delete counters for each to
        // count the deletes
        let del = [ 0, 0 ];
   
        // Counters to keep track
        // of characters left from each type
        let count = [ 0, 0 ];
   
        // Queue to simulate the process
        let q = [];
   
        // Initializing the queue
        for (let i = 0; i < N; i++) {
            let x = (c[i] == '1' ? 1 : 0);
            count[x]++;
            q.push(x);
        }   
         
        // Looping till at least 1 digit is
        // left from both the type
        while (count[0] > 0 && count[1] > 0) {
            let t = q.shift();
   
            // If there is a floating delete for
            // current character we will
            // delete it and move forward otherwise
            // we will increase delete counter for
            // opposite digit
            if (del[t] > 0) {
                del[t]--;
                count[t]--;
            }
            else {
                del[t ^ 1]++;
                q.push(t);
            }
        }
   
        // If 0 are left
        // then answer is 0 else
        // answer is 1
        if (count[0] > 0)
            return "0";
        return "1";
}
 
// Driver Code
 
let S = "1010100100000";
   
// Length of String
let N = S.length;
 
// Printing answer
document.write(remainingDigit(S, N));
 
 
// This code is contributed by unknown2108
</script>

0

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