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
- If S[i] is equal to 1, increment the value of count1 by 1.
- Otherwise, increment the value of count0 by 1.
- 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 Codeint main(){ // Given string string s = "010100"; // Function Call if (isPossible(s)) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java program for the above approachpublic 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 Codepublic 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 Codeif __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 approachusing 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 codestatic 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 stringlet s = "010100";// Function Callif (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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Find More Info here to that Topic: geeksforgeeks.org/check-if-a-binary-string-can-be-split-into-disjoint-subsequences-which-are-equal-to-010/ […]
… [Trackback]
[…] There you will find 471 additional Information on that Topic: geeksforgeeks.org/check-if-a-binary-string-can-be-split-into-disjoint-subsequences-which-are-equal-to-010/ […]
… [Trackback]
[…] Find More here to that Topic: geeksforgeeks.org/check-if-a-binary-string-can-be-split-into-disjoint-subsequences-which-are-equal-to-010/ […]