- binary-string, Bit Magic, frequency-counting, Greedy, partition, Strings, subsequence

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

Check if a Binary String can be split into disjoint subsequences which are equal to “010”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: YesExplanation: Partitioning the string in the manner 010100 to generate two subsequences equal to “010”.Input: S = “010000”Output: NoApproach: 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 iIf 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++#include using namespace std;bool isPossible(string s){            int n = s.size();        int count_0 = 0, count_1 = 0;            for (int i = 0; i < n; i++) {                        if (s[i] == '0')            ++count_0;                        else            ++count_1;                                if (count_1 > count_0)            return false;    }                if (count_0 != (2 * count_1))        return false;        count_0 = 0, count_1 = 0;            for (int i = n – 1; i >= 0; –i) {                        if (s[i] == ‘0’)            ++count_0;                        else            ++count_1;                        if (count_1 > count_0)            return false;    }    return true;}int main(){        string s = “010100”;        if (isPossible(s))        cout count_0):            return False    return Trueif __name__ == ‘__main__’:             s = “010100”        if (isPossible(s)):        print(“Yes”)    else:        print(“No”)Output: YesTime Complexity: O(N) Auxiliary Space: O(1)Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.  To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.In case you wish to attend live classes with industry experts, please refer Geeks Classes Live