La string más pequeña obtenida al eliminar todas las apariciones de 01 y 11 de Binary String | conjunto 2

Dada una string binaria S de longitud N , “01” “11”

Ejemplos:

Entrada: S = “1010”
Salida: 2
Explicación:  La eliminación de la substring “01” modifica la string S a “10”.

Entrada: S = “111”
Salida: 1 

Enfoque basado en la pila : consulte el artículo anterior para encontrar la longitud de la string más pequeña posible mediante operaciones dadas.

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

Enfoque optimizado para el espacio: el enfoque anterior se puede optimizar para el espacio almacenando solo la longitud de los caracteres que no se eliminan.

• Inicialice una variable, digamos st como 0, para almacenar la longitud de la string más pequeña posible.
• Iterar sobre los caracteres de la string S y realizar los siguientes pasos:
  • Si st es mayor que 0 y S[i] es igual a ‘ 1 ‘, extraiga el último elemento disminuyendo st en 1 .
  • De lo contrario, incremente st en 1.
• Finalmente, después de completar los pasos anteriores, imprima la respuesta obtenida en st .

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the length of
// the smallest string possible by
// removing substrings "01" and "11"
int shortestString(string S, int N)
{
    // Stores the length of
    // the smallest string
    int st = 0;
 
    // Traverse the string S
    for (int i = 0; i < N; i++) {
 
        // If st is greater
        // than 0 and S[i] is '1'
        if (st && S[i] == '1') {
 
            // Delete the last
            // character and
            // decrement st by 1
            st--;
        }
 
        // Otherwise
        else {
 
            // Increment st by 1
            st++;
        }
    }
 
    // Return the answer in st
    return st;
}
 
// Driver Code
int main()
{
    // Input
    string S = "1010";
 
    int N = S.length();
 
    // Function call
    cout << shortestString(S, N);
    return 0;
}

// Java program for the above approach
public class GFG_JAVA {
 
    // Function to find the length of
    // the smallest string possible by
    // removing substrings "01" and "11"
    static int shortestString(String S, int N)
    {
        // Stores the length of
        // the smallest string
        int st = 0;
 
        // Traverse the string S
        for (int i = 0; i < N; i++) {
 
            // If st is greater
            // than 0 and S[i] is '1'
            if (st > 0 && S.charAt(i) == '1') {
 
                // Delete the last
                // character and
                // decrement st by 1
                st--;
            }
 
            // Otherwise
            else {
 
                // Increment st by 1
                st++;
            }
        }
 
        // Return the answer in st
        return st;
    }
 
    // Driver code
    public static void main(String[] args)
    {
      // Input
        String S = "1010";
        int N = S.length();
 
        // Function call
        System.out.println(shortestString(S, N));
    }
}
 
// This code is contributed by abhinavjain194

# Python3 program for the above approach
 
# Function to find the length of
# the smallest string possible by
# removing substrings "01" and "11"
def shortestString(S, N) :
     
    # Stores the length of
    # the smallest string
    st = 0;
 
    # Traverse the string S
    for i in range(N) :
 
        # If st is greater
        # than 0 and S[i] is '1'
        if (st and S[i] == '1') :
 
            # Delete the last
            # character and
            # decrement st by 1
            st -= 1;
 
        # Otherwise
        else :
 
            # Increment st by 1
            st += 1;
 
    # Return the answer in st
    return st;
 
# Driver Code
if __name__ == "__main__" :
 
    # Input
    S = "1010";
 
    N = len(S);
 
    # Function call
    print(shortestString(S, N));
     
    # This code is contributed by AnkThon

// C# program for the above approach
using System;
public class GFG_JAVA {
 
    // Function to find the length of
    // the smallest string possible by
    // removing substrings "01" and "11"
    static int shortestString(string S, int N)
    {
       
        // Stores the length of
        // the smallest string
        int st = 0;
 
        // Traverse the string S
        for (int i = 0; i < N; i++) {
 
            // If st is greater
            // than 0 and S[i] is '1'
            if (st > 0 && S[i] == '1') {
 
                // Delete the last
                // character and
                // decrement st by 1
                st--;
            }
 
            // Otherwise
            else {
 
                // Increment st by 1
                st++;
            }
        }
 
        // Return the answer in st
        return st;
    }
 
    // Driver code
    public static void Main(string[] args)
    {
      // Input
        string S = "1010";
        int N = S.Length;
 
        // Function call
        Console.WriteLine(shortestString(S, N));
    }
}
 
// This code is contributed by AnkThon

<script>
    // Javascript program for the above approach
     
    // Function to find the length of
    // the smallest string possible by
    // removing substrings "01" and "11"
    function shortestString(S, N)
    {
        
        // Stores the length of
        // the smallest string
        let st = 0;
  
        // Traverse the string S
        for (let i = 0; i < N; i++) {
  
            // If st is greater
            // than 0 and S[i] is '1'
            if (st > 0 && S[i] == '1') {
  
                // Delete the last
                // character and
                // decrement st by 1
                st--;
            }
  
            // Otherwise
            else {
  
                // Increment st by 1
                st++;
            }
        }
  
        // Return the answer in st
        return st;
    }
     
    // Input
    let S = "1010";
    let N = S.length;
 
    // Function call
    document.write(shortestString(S, N));
     
    // This code is contributed by divyeshrabadiya07.
</script>

2

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