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:
- Inicialice una variable booleana, res como verdadera para verificar si la string S cumple o no con la condición dada.
- Cree dos variables, count0 y count1 para almacenar la frecuencia de 0 y 1 en la string , S.
- Recorra la string , S en el rango [0, N – 1] usando la variable i
- Si S[i] es igual a 1 , incremente el valor de count1 en 1 .
- De lo contrario, incremente el valor de count0 en 1 .
- Compruebe si el valor de count1 > count0 , luego actualice res como falso .
- Compruebe si el valor de count0 no es igual a 2 * count1 , luego actualice res como falso .
- Restablece el valor de count0 y count1 a 0 .
- Atraviese la cuerda S en la dirección inversa y repita los pasos 3.1 a 3.3 .
- 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++
// 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
// 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
# 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#
// 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
Javascript
<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>
Producción:
Yes
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por shrayansh95 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA