Given 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: 3
Explanation:
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: 4
Approach: 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++
// C++ program for the above approach#include <iostream>using namespace std;// Function to count the maximum number// of operations performed on the stringvoid countOperations(string S){ // Size of the string int n = S.length(); // Stores the maximum number of // operations performed int ans = 0; // Stores the count of 'X' occurred // so far int cnt = 0; // Traverse the string for (int i = 0; i < n; i++) { // Check if current char // is 'X' if (S[i] == '0') { cnt++; } else { // Check if the value of // cnt is greater than 0 if (cnt > 0) { // Decrement the value // of cnt cnt--; // Increment the value // of ans ans++; } } } // Print the value of ans cout << ans;}// Driver Codeint main(){ string S = "110011010"; countOperations(S); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG{ // Function to count the maximum number // of operations performed on the string public static void countOperations(String S) { // Size of the string int n = S.length(); // Stores the maximum number of // operations performed int ans = 0; // Stores the count of 'X' occurred // so far int cnt = 0; // Traverse the string for (int i = 0; i < n; i++) { // Check if current char // is 'X' if (S.charAt(i) == '0') { cnt++; } else { // Check if the value of // cnt is greater than 0 if (cnt > 0) { // Decrement the value // of cnt cnt--; // Increment the value // of ans ans++; } } } // Print the value of ans System.out.println(ans); } // Driver code public static void main (String[] args) { String S = "110011010"; countOperations(S); }}// This code is contributed by Manu Pathria |
Python3
# Python program for the above approach# Function to count the maximum number# of operations performed on the stringdef countOperations(S): # Size of the string n = len(S) # Stores the maximum number of # operations performed ans = 0 # Stores the count of 'X' occurred # so far cnt = 0 # Traverse the string for i in range(n): # Check if current char # is 'X' if (S[i] == '0'): cnt+=1 else: # Check if the value of # cnt is greater than 0 if (cnt > 0): # Decrement the value # of cnt cnt-=1 # Increment the value # of ans ans+=1 # Print value of ans print (ans)# Driver Codeif __name__ == '__main__': S = "110011010" countOperations(S)# This code is contributed by mohit kumar 29. |
C#
// C# program for the above approachusing System;class GFG{ // Function to count the maximum number // of operations performed on the string public static void countOperations(string S) { // Size of the string int n = S.Length; // Stores the maximum number of // operations performed int ans = 0; // Stores the count of 'X' occurred // so far int cnt = 0; // Traverse the string for (int i = 0; i < n; i++) { // Check if current char // is 'X' if (S[i] == '0') { cnt++; } else { // Check if the value of // cnt is greater than 0 if (cnt > 0) { // Decrement the value // of cnt cnt--; // Increment the value // of ans ans++; } } } // Print the value of ans Console.Write(ans); } // Driver code public static void Main (string[] args) { string S = "110011010"; countOperations(S); }}// This code is contributed by ukasp. |
Javascript
<script> // JavaScript Program for the above approach // Function to count the maximum number // of operations performed on the string function countOperations(S) { // Size of the string let n = S.length; // Stores the maximum number of // operations performed let ans = 0; // Stores the count of 'X' occurred // so far let cnt = 0; // Traverse the string for (let i = 0; i < n; i++) { // Check if current char // is 'X' if (S[i] == '0') { cnt++; } else { // Check if the value of // cnt is greater than 0 if (cnt > 0) { // Decrement the value // of cnt cnt--; // Increment the value // of ans ans++; } } } // Print the value of ans document.write(ans); } // Driver Code let S = "110011010"; countOperations(S); // This code is contributed by Potta Lokesh </script> |
Output:
3
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!
