Compruebe si una string binaria se puede dividir en subsecuencias disjuntas que son iguales a «010»

Dada una string binaria , S de tamaño N , la tarea es verificar si es posible dividir la string en subsecuencias disjuntas iguales a «010» .

Ejemplos:

Entrada: S = “010100”
Salida: Si
Explicación: Particionando la string de la manera 01 010 0 para generar dos subsecuencias iguales a “010”.

Entrada: S = “010000”
Salida: No

Enfoque: La idea se basa en la observación de que una string binaria dada no cumplirá la condición requerida si alguna de las siguientes condiciones se cumple:

• Si, en cualquier punto, el conteo de prefijos de ‘1’ es mayor que el conteo de prefijos de ‘0’ s.
• Si, en cualquier punto, el conteo de sufijos de ‘1’ es mayor que el conteo de sufijos de ‘0’ s.
• Si el conteo de ‘0’ s no es igual al doble del conteo de ‘1’ s en toda la string.

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

1. Inicialice una variable booleana, res como verdadera para verificar si la string S cumple o no con la condición dada.
2. Cree dos variables, count0 y count1 para almacenar la frecuencia de 0 y 1 en la string , S.
3. Recorra la string , S en el rango [0, N – 1] usando la variable i
   1. Si S[i] es igual a 1 , incremente el valor de count1 en 1 .
   2. De lo contrario, incremente el valor de count0 en 1 .
   3. Compruebe si el valor de count1 > count0 , luego actualice res como falso .
4. Compruebe si el valor de count0 no es igual a 2 * count1 , luego actualice res como falso .
5. Restablece el valor de count0 y count1 a 0 .
6. Atraviese la cuerda S en la dirección inversa y repita los pasos 3.1 a 3.3 .
7. Si el valor de res sigue siendo verdadero , imprima «Sí» como resultado; de lo contrario, imprima «No» .

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 check if the given string
// can be partitioned into a number of
// subsequences all of which are equal to "010"
bool isPossible(string s)
{
    // Store the size
    // of the string
    int n = s.size();
 
    // Store the count of 0s and 1s
    int count_0 = 0, count_1 = 0;
 
    // Traverse the given string
    // in the forward direction
    for (int i = 0; i < n; i++) {
 
        // If the character is '0',
        // increment count_0 by 1
        if (s[i] == '0')
            ++count_0;
 
        // If the character is '1'
        // increment count_1 by 1
        else
            ++count_1;
 
        // If at any point,
        // count_1 > count_0,
        // return false
        if (count_1 > count_0)
            return false;
    }
 
    // If count_0 is not equal
    // to twice count_1,
    // return false
    if (count_0 != (2 * count_1))
        return false;
 
    // Reset the value of count_0 and count_1
    count_0 = 0, count_1 = 0;
 
    // Traverse the string in
    // the reverse direction
    for (int i = n - 1; i >= 0; --i) {
 
        // If the character is '0'
        // increment count_0
        if (s[i] == '0')
            ++count_0;
 
        // If the character is '1'
        // increment count_1
        else
            ++count_1;
 
        // If count_1 > count_0,
        // return false
        if (count_1 > count_0)
            return false;
    }
 
    return true;
}
 
// Driver Code
int main()
{
    // Given string
    string s = "010100";
 
    // Function Call
    if (isPossible(s))
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}

// Java program for the above approach
public class MyClass
{
  
// Function to check if the given string
// can be partitioned into a number of
// subsequences all of which are equal to "010"
static boolean isPossible(String s)
{
   
    // Store the size
    // of the string
    int n = s.length();
 
    // Store the count of 0s and 1s
    int count_0 = 0, count_1 = 0;
 
    // Traverse the given string
    // in the forward direction
    for (int i = 0; i < n; i++) {
 
        // If the character is '0',
        // increment count_0 by 1
        if (s.charAt(i) == '0')
            ++count_0;
 
        // If the character is '1'
        // increment count_1 by 1
        else
            ++count_1;
 
        // If at any point,
        // count_1 > count_0,
        // return false
        if (count_1 > count_0)
            return false;
    }
 
    // If count_0 is not equal
    // to twice count_1,
    // return false
    if (count_0 != (2 * count_1))
        return false;
 
    // Reset the value of count_0 and count_1
    count_0 = 0; count_1 = 0;
 
    // Traverse the string in
    // the reverse direction
    for (int i = n - 1; i >= 0; --i) {
 
        // If the character is '0'
        // increment count_0
        if (s.charAt(i) == '0')
            ++count_0;
 
        // If the character is '1'
        // increment count_1
        else
            ++count_1;
 
        // If count_1 > count_0,
        // return false
        if (count_1 > count_0)
            return false;
    }
 
    return true;
}
 
// Driver Code
public static void main(String args[])
{
    // Given string
    String s = "010100";
 
    // Function Call
    if (isPossible(s))
         System.out.println("Yes");
    else
        System.out.println("No");
}
}
 
// This code is contributed by SoumikMondal

# Python3 program for the above approach
 
# Function to check if the given string
# can be partitioned into a number of
# subsequences all of which are equal to "010"
def isPossible(s):
     
    # Store the size
    # of the string
    n = len(s)
 
    # Store the count of 0s and 1s
    count_0, count_1 = 0, 0
 
    # Traverse the given string
    # in the forward direction
    for i in range(n):
 
        # If the character is '0',
        # increment count_0 by 1
        if (s[i] == '0'):
            count_0 += 1
 
        # If the character is '1'
        # increment count_1 by 1
        else:
            count_1 += 1
 
        # If at any point,
        # count_1 > count_0,
        # return false
        if (count_1 > count_0):
            return False
  
    # If count_0 is not equal
    # to twice count_1,
    # return false
    if (count_0 != (2 * count_1)):
        return False
 
    # Reset the value of count_0 and count_1
    count_0, count_1 = 0, 0
 
    # Traverse the string in
    # the reverse direction
    for i in range(n - 1, -1, -1):
         
        # If the character is '0'
        # increment count_0
        if (s[i] == '0'):
            count_0 += 1
 
        # If the character is '1'
        # increment count_1
        else:
            count_1 += 1
 
        # If count_1 > count_0,
        # return false
        if (count_1 > count_0):
            return False
 
    return True
 
# Driver Code
if __name__ == '__main__':
     
    # Given string
    s = "010100"
 
    # Function Call
    if (isPossible(s)):
        print("Yes")
    else:
        print("No")
 
# This code is contributed by mohit kumar 29

// C# program for the above approach
using System;
 
class GFG{
     
// Function to check if the given string
// can be partitioned into a number of
// subsequences all of which are equal to "010"
static bool isPossible(String s)
{
     
    // Store the size
    // of the string
    int n = s.Length;
 
    // Store the count of 0s and 1s
    int count_0 = 0, count_1 = 0;
 
    // Traverse the given string
    // in the forward direction
    for(int i = 0; i < n; i++)
    {
         
        // If the character is '0',
        // increment count_0 by 1
        if (s[i] == '0')
            ++count_0;
 
        // If the character is '1'
        // increment count_1 by 1
        else
            ++count_1;
 
        // If at any point,
        // count_1 > count_0,
        // return false
        if (count_1 > count_0)
            return false;
    }
 
    // If count_0 is not equal
    // to twice count_1,
    // return false
    if (count_0 != (2 * count_1))
        return false;
 
    // Reset the value of count_0 and count_1
    count_0 = 0;
    count_1 = 0;
 
    // Traverse the string in
    // the reverse direction
    for(int i = n - 1; i >= 0; --i)
    {
         
        // If the character is '0'
        // increment count_0
        if (s[i] == '0')
            ++count_0;
 
        // If the character is '1'
        // increment count_1
        else
            ++count_1;
 
        // If count_1 > count_0,
        // return false
        if (count_1 > count_0)
            return false;
    }
    return true;
}
 
// Driver code
static public void Main()
{
 
    // Given string
    String s = "010100";
     
    // Function Call
    if (isPossible(s))
        Console.Write("Yes");
    else
        Console.Write("No");
}
}
 
// This code is contributed by offbeat

<script>
 
// JavaScript program for the above approach
 
// Function to check if the given string
// can be partitioned into a number of
// subsequences all of which are equal to "010"
function isPossible(s)
{
    // Store the size
    // of the string
    let n = s.length;
  
    // Store the count of 0s and 1s
    let count_0 = 0, count_1 = 0;
  
    // Traverse the given string
    // in the forward direction
    for (let i = 0; i < n; i++) {
  
        // If the character is '0',
        // increment count_0 by 1
        if (s[i] == '0')
            ++count_0;
  
        // If the character is '1'
        // increment count_1 by 1
        else
            ++count_1;
  
        // If at any point,
        // count_1 > count_0,
        // return false
        if (count_1 > count_0)
            return false;
    }
  
    // If count_0 is not equal
    // to twice count_1,
    // return false
    if (count_0 != (2 * count_1))
        return false;
  
    // Reset the value of count_0 and count_1
    count_0 = 0; count_1 = 0;
  
    // Traverse the string in
    // the reverse direction
    for (let i = n - 1; i >= 0; --i) {
  
        // If the character is '0'
        // increment count_0
        if (s[i] == '0')
            ++count_0;
  
        // If the character is '1'
        // increment count_1
        else
            ++count_1;
  
        // If count_1 > count_0,
        // return false
        if (count_1 > count_0)
            return false;
    }
  
    return true;
}
 
// Driver Code
// Given string
let s = "010100";
 
// Function Call
if (isPossible(s))
    document.write("Yes");
else
    document.write("No");
 
 
// This code is contributed by unknown2108
 
</script>

Yes

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