Maximize the number of times a character can be removed from substring 01 from given Binary String
Given a binary string S of size N, the task is to find the maximum number of operations that can be performed on S, by selecting any substring β01β and removing any character from it in a single move, reducing the length of the string by 1.
Examples:
Input: S = β001111β, N = 6
Output: 5
Explanation:
One way to perform the operations is:
- Select the substring β01β over the range [1, 2] and erase the S[2] ( = β1β). The string modifies to β00111β.
- Select the substring β01β over the range [1, 2] and erase the S[2] ( = β1β). The string modifies to β0011β.
- Select the substring β01β over the range [1, 2] and erase the S[2] ( = β1β). The string modifies to β001β.
- Select the substring β01β over the range [1, 2] and erase the S[1] ( = β0β). The string modifies to β01β.
- Select the substring β01β over the range [0, 1] and erase the S[1] ( = β1β). The string modifies to β0β.
- Now no characters can be removed.
Therefore, the total number of operations performed is 5, which is the maximum possible.
Input: S=β0101β³, N=4
Output: 3
Approach: The given problem can be solved based on the following observations:
- Any 1s present in the prefix of S cannot be removed because there are no 0s before them.
- Any 0s present in the suffix of S cannot be removed because there are no 1s after them.
- All other characters are removable.
- If there are X removable characters, at most X-1 operations can be performed because, eventually, only a single character will remain which cannot be removed.
Follow the steps below to solve the problem:
- Initialize two variables, say X and Y as 0, which store the number of 0s in the suffix and the number of 1s in the prefix respectively, which cannot be removed.
- Iterate over the characters of the string S and perform the following steps:
- If the current character is β1β², increment Y by 1.
- Otherwise, stop traversing.
- Iterate over the characters of the string S in reverse order and perform the following steps:
- If the current character is 0, increment X by 1.
- Otherwise, stop traversing.
- If the sum of X and Y is equal to N, print 0 as there are no removable characters.
- Otherwise, print N-(X+Y)-1 as the answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the maximum moves // that can be performed on a string int maxOperations(string S, int N) { // Stores 0s in suffix int X = 0; // Stores 1s in prefix int Y = 0; // Iterate over the characters of // the string for ( int i = 0; i < N; i++) { if (S[i] == '0' ) break ; Y++; } // Iterate until i is greater than // or equal to 0 for ( int i = N - 1; i >= 0; i--) { if (S[i] == '1' ) break ; X++; } // If N is equal to x+y if (N == X + Y) return 0; // Return answer return N - (X + Y) - 1; } // Driver code int main() { // Input string S = "001111" ; int N = S.length(); // Function call cout << maxOperations(S, N) << endl; return 0; } |
Java
// Java program for the above approach import java.io.*; class GFG{ // Function to find the maximum moves // that can be performed on a string static int maxOperations(String S, int N) { // Stores 0s in suffix int X = 0 ; // Stores 1s in prefix int Y = 0 ; // Iterate over the characters of // the string for ( int i = 0 ; i < N; i++) { if (S.charAt(i) == '0' ) break ; Y++; } // Iterate until i is greater than // or equal to 0 for ( int i = N - 1 ; i >= 0 ; i--) { if (S.charAt(i) == '1' ) break ; X++; } // If N is equal to x+y if (N == X + Y) return 0 ; // Return answer return N - (X + Y) - 1 ; } // Driver code public static void main(String[] args) { // Input String S = "001111" ; int N = S.length(); // Function call System.out.println(maxOperations(S, N)); } } // This code is contributed by sanjoy_62 |
Python3
# Python3 program for the above approach # Function to find the maximum moves # that can be performed on a string def maxOperations(S, N): # Stores 0s in suffix X = 0 # Stores 1s in prefix Y = 0 # Iterate over the characters of # the string for i in range (N): if (S[i] = = '0' ): break Y + = 1 # Iterate until i is greater than # or equal to 0 i = N - 1 while (i > = 0 ): if (S[i] = = '1' ): break X + = 1 # If N is equal to x+y if (N = = X + Y): return 0 # Return answer return N - (X + Y) - 1 # Driver code if __name__ = = '__main__' : # Input S = "001111" N = len (S) # Function call print (maxOperations(S, N)) # This code is contributed by SURENDRA_GANGWAR |
C#
// C# program for the above approach using System; class GFG{ // Function to find the maximum moves // that can be performed on a string static int maxOperations(String S, int N) { // Stores 0s in suffix int X = 0; // Stores 1s in prefix int Y = 0; // Iterate over the characters of // the string for ( int i = 0; i < N; i++) { if (S[i] == '0' ) break ; Y++; } // Iterate until i is greater than // or equal to 0 for ( int i = N - 1; i >= 0; i--) { if (S[i] == '1' ) break ; X++; } // If N is equal to x+y if (N == X + Y) return 0; // Return answer return N - (X + Y) - 1; } // Driver code static void Main() { // Input String S = "001111" ; int N = S.Length; // Function call Console.WriteLine(maxOperations(S, N)); } } // This code is contributed by abhinavjain194 |
Javascript
<script> // JavaScript program for the above approach // Function to find the maximum moves // that can be performed on a string function maxOperations(S, N) { // Stores 0s in suffix let X = 0; // Stores 1s in prefix let Y = 0; // Iterate over the characters of // the string for (let i = 0; i < N; i++) { if (S[i] == '0' ) break ; Y++; } // Iterate until i is greater than // or equal to 0 for (let i = N - 1; i >= 0; i--) { if (S[i] == '1' ) break ; X++; } // If N is equal to x+y if (N == X + Y) return 0; // Return answer return N - (X + Y) - 1; } // Driver Code // Input let S = "001111" ; let N = S.length; // Function call document.write(maxOperations(S, N)); </script> |
Output
5
Time complexity: O(N)
Auxiliary Space: O(1)
Contact Us