# Maximum count of “010..” subsequences that can be removed from given Binary String

Maximum count of “010..” subsequences that can be removed from given Binary StringGiven a binary string S consisting of size N, the task is to find the maximum number of binary subsequences of the form “010..” of length at least 2 that can be removed from the given string S.Examples:Input: S = “110011010”Output: 3Explanation:Following are the subsequence removed:Operation 1: Choose the subsequence as “01” of indices {2, 4}, and deleting it modifies the string S = “1101010”.Operation 2: Choose the subsequence as “01” of indices {2, 3}, and deleting it modifies the string S = “11010”.Operation 3: Choose the subsequence as “01” of indices {2, 3}, and deleting it modifies the string S = “110”.From the above observations, the maximum number of times subsequence is removed is 3.Input: S = “00111110011”Output: 4Approach: The given problem can be solved by removing the subsequence of type “01” every time to maximize the number of subsequences removed. Therefore, this can be maintained by keeping a variable that stores the count of the number of characters 0. Follow the steps below to solve the problem:Initialize a variable, say cnt as 0 to store the count of the number of 0s that have occurred in the string.Initialize variable, say ans as 0 to count the total number of removal operations performed.Traverse the string, S using the variable i and perform the following steps:If the value of S[i] is X then increment the value of cnt by 1.Otherwise, if the value of cnt is greater than 0, then decrement the value of cnt and increment the value of ans by 1.After completing the above steps, print the value of ans as the result.Below is the implementation of the above approach:C++ #include using namespace std; void countOperations(string S){ int n = S.length(); int ans = 0; int cnt = 0; for (int i = 0; i < n; i++) { if (S[i] == '0') { cnt++; } else { if (cnt > 0) { cnt–; ans++; } } } cout