Cuente las strings binarias de la misma longitud que la string dada después de eliminar las substrings «01» y «00» que consisten en al menos un ‘1’

Dada una string binaria S , la tarea es contar strings binarias totales que consisten en al menos un ‘1’ de longitud igual a la longitud de la string dada después de eliminar repetidamente todas las ocurrencias de substrings «10» y «00» de la string dada .

Ejemplos:

Entrada: S = «111»
Salida: 7
Explicación: Dado que no hay ocurrencias de «10» o «01» en la string dada, la longitud de la string restante es 3. Todas las strings binarias posibles de longitud 3 que consisten en al menos una los bits establecidos son {“001”, “010”, “011”, “100”, “101”, “110”, “111”}

Entrada: S = “0101”
Salida: 3
Explicación: Después de borrar “10”, S = “01”. Por lo tanto, la longitud de la string restante es 2. Las strings de longitud 2 que constan de al menos un bit establecido son {“01”, “10”, “11”}

Enfoque: la idea es calcular la longitud de la string dada después de eliminar todas las substrings de la forma «10» y «00» . Considerando el resto; longitud de la string sea N , el número total de strings que consta de al menos un bit establecido será igual a 2 ^N -1 .

Siga los pasos a continuación para resolver el problema:

1. Inicializar una variable, digamos contar .
2. Iterar sobre los caracteres de la string S . Para cada carácter, verifique si es ‘0’ y si el conteo es mayor que 0 o no. Si se determina que es cierto, disminuya el conteo en 1 .
3. De lo contrario, si el carácter actual es ‘1’ , incremente la cuenta en 1 .
4. Después de completar el recorrido de la string, imprima 2 ^conteos – 1 como la respuesta requerida.

 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 count the strings
// consisting of at least 1 set bit
void countString(string S)
{
    // Initialize count
    long long count = 0;
 
    // Iterate through string
    for (auto it : S) {
 
        if (it == '0' and count > 0) {
            count--;
        }
        else {
            count++;
        }
    }
 
    // The answer is 2^N-1
    cout << ((1 << count) - 1) << "\n";
}
 
// Driver Code
int main()
{
 
    // Given string
    string S = "1001";
 
    // Function call
    countString(S);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
   
class GFG{
   
// Function to count the strings
// consisting of at least 1 set bit
static void countString(String S)
{
     
    // Initialize count
    int count = 0;
     
    // Iterate through string
    for(char it : S.toCharArray())
    {
        if (it == '0' && count > 0)
        {
            count--;
        }
        else
        {
            count++;
        }
    }
  
    // The answer is 2^N-1
    System.out.print((1 << count) - 1);
}
   
// Driver Code
public static void main(String[] args)
{
     
    // Given string
    String S = "1001";
  
    // Function call
    countString(S);
}
}
 
// This code is contributed by susmitakundugoaldanga

# Python3 program for the
# above approach 
 
# Function to count the
# strings consisting of
# at least 1 set bit
def countString(S):
   
    # Initialize count
    count = 0
     
    # Iterate through
    # string
    for i in S:
        if (i == '0' and
            count > 0):           
            count -= 1
         
        else:           
            count += 1
 
    # The answer is 2^N-1    
    print((1 << count) - 1) 
 
# Driver Code
if __name__ == "__main__":
 
    # Given string   
    S = "1001"
     
    # Function call   
    countString(S)
 
# This code is contributed by Virusbuddah_

// C# program for the above approach
using System;
   
class GFG{
   
// Function to count the strings
// consisting of at least 1 set bit
static void countString(string S)
{
     
    // Initialize count
    int count = 0;
     
    // Iterate through string
    foreach(char it in S)
    {
        if (it == '0' && count > 0)
        {
            count--;
        }
        else
        {
            count++;
        }
    }
  
    // The answer is 2^N-1
    Console.Write((1 << count) - 1);
}
   
// Driver Code
public static void Main(string[] args)
{
     
    // Given string
    string S = "1001";
  
    // Function call
    countString(S);
}
}
 
// This code is contributed by chitranayal

<script>
// javascript program for the above approach
 
    // Function to count the strings
    // consisting of at least 1 set bit
    function countString( S) {
 
        // Initialize count
        var count = 0;
 
        // Iterate through string
        for (var it =0;it< S.length; it++) {
            if (S[it] == '0' && count > 0) {
                count--;
            } else {
                count++;
            }
        }
 
        // The answer is 2^N-1
        document.write((1 << count) - 1);
    }
 
    // Driver Code
     
 
        // Given string
        var S = "1001";
 
        // Function call
        countString(S);
 
// This code contributed by umadevi9616
</script>

3

Complejidad de tiempo: O(L) donde L es la longitud de la string. 
Espacio Auxiliar: O(1)