Check if a Binary String can be split into disjoint subsequences which are equal to “010”

0 0 7 minutes read

Given a binary string, S of size N, the task is to check if it is possible to partition the string into disjoint subsequences equal to “010”.

Examples:

Input: S = “010100”
Output: Yes
Explanation: Partitioning the string in the manner 010100 to generate two subsequences equal to “010”.

Input: S = “010000”
Output: No

Approach: The idea is based on the observation that a given binary string will not satisfy the required condition if any of the following conditions holds true:

If, at any point, the prefix count of ‘1’s is greater than the prefix count of ‘0’s.
If, at any point, the suffix count of ‘1’s is greater than the suffix count of ‘0’s.
If the count of ‘0’s is not equal to twice the count of ‘1’s in the entire string.

Follow the steps below to solve the problem:

Initialize a boolean variable, res as true to check if the string, S satisfies the given condition or not.
Create two variables, count0 and count1 to store the frequency of 0s and 1s in the string, S.
Traverse the string, S in the range [0, N – 1] using the variable i
1. If S[i] is equal to 1, increment the value of count1 by 1.
2. Otherwise, increment the value of count0 by 1.
3. Check if the value of count1 > count0, then update res as false.
Check if the value of count0 is not equal to 2 * count1, then update res as false.
Reset the value of count0 and count1 to 0.
Traverse the string S in the reverse direction and repeat steps 3.1 to 3.3.
If the value of res is still true, print “Yes” as the result, otherwise print “No”.

Below is the implementation of the above approach:

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>

Output:

Yes

Time Complexity: O(N)
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!