Minimum removals required to place all 0s before 1s in a Binary String
Given a binary string S, the task is to find the minimum number of characters required to be removed from S, such that all the 0s are placed before 1s.
Examples:
Input: S = β001101β
Output: 1
Explanation:
Removing S[4] (= β0β) modifies the string S to β00111β.
Therefore, minimum number of deletions required is 1.Input: S = 01001
Output: 1
Explanation:
Removing S[1] (= β1β) modifies the string S to β0001β.
Therefore, minimum number of deletions required is 1.
Approach: The problem can be solved by finding the minimum number of β0βs characters required to be deleted from the right, say right_0, and the minimum number of β1βs required to be deleted from the left, say left_1, to obtain the required string. The minimum sum of right_0 and left_0 obtained for any index gives the final result.
Follow the steps below to solve the given problem:
- Initialize two counter variables, say right_0 and left_1.
- Store the count of β0βs in the string S in right_0 and set left_1 equal to 0.
- Initialize a variable, say res, to store the required answer.
- Iterate over the characters of the string S and for each character:
- Check if s[i] is equal to β0β or not.
- If found to be true, then decrease right_0 by 1.
- Otherwise, increase left_1 by 1.
- Check if the sum right_0, left_1 is less than res or not. If found to be true, then update res equal to the minimum of res and right_0 + left_1.
- Check if s[i] is equal to β0β or not.
- After complete traversal of the array, print res as the required 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 count minimum removals // required to arrange all 0s before 1s int minimumDeletions(string s) { // Count the occurrences of 0 in s int right_0 = count(s.begin(), s.end(), '0' ); int left_1 = 0; // Size of the string int n = s.size(); // Stores the minimum // number of removals required int res = INT_MAX; // Iterate over each of the // characters in the string s for ( int i = 0; i < n; i++) { // If the i-th character // is found to be '0' if (s[i] == '0' ) { right_0 -= 1; } else { left_1 += 1; } // Store the minimum of res // and right_0 + left_1 in res res = min(res, right_0 + left_1); } // Return the final result return res; } // Driver Code int main() { string s = "001101" ; int count = minimumDeletions(s); cout << count; return 0; } |
Java
// Java program to implement // the above approach import java.util.*; class GFG{ // Function to count minimum removals // required to arrange all 0s before 1s static int minimumDeletions(String s) { // Count the occurrences of 0 in s int right_0 = ( int )(s.chars().filter(ch -> ch == '0' ).count()); int left_1 = 0 ; // Size of the string int n = s.length(); // Stores the minimum // number of removals required int res = Integer.MAX_VALUE; // Iterate over each of the // characters in the string s for ( int i = 0 ; i < n; i++) { // If the i-th character // is found to be '0' if (s.charAt(i) == '0' ) { right_0 -= 1 ; } else { left_1 += 1 ; } // Store the minimum of res // and right_0 + left_1 in res res = Math.min(res, right_0 + left_1); } // Return the final result return res; } // Driver Code public static void main(String[] args) { String s = "001101" ; int count = minimumDeletions(s); System.out.print(count); } } // This code is contributed by sanjoy_62. |
Python3
# Python3 program for the above approach import sys # Function to count minimum removals # required to arrange all 0s before 1s def minimumDeletions(s) : # Count the occurrences of 0 in s right_0 = s.count( '0' ) left_1 = 0 # Size of the string n = len (s) # Stores the minimum # number of removals required res = sys.maxsize # Iterate over each of the # characters in the string s for i in range (n): # If the i-th character # is found to be '0' if (s[i] = = '0' ) : right_0 - = 1 else : left_1 + = 1 # Store the minimum of res # and right_0 + left_1 in res res = min (res, right_0 + left_1) # Return the final result return res # Driver Code s = "001101" count = minimumDeletions(s) print ( count) # This code is contributed by splevel62. |
C#
// C# program for above approach using System; using System.Collections.Generic; public class GFG { // Function to count minimum removals // required to arrange all 0s before 1s static int minimumDeletions( string s) { // Count the occurrences of 0 in s int right_0 = ( int )s.Split( '0' ).Length - 1; int left_1 = 0; // Size of the string int n = s.Length; // Stores the minimum // number of removals required int res = Int32.MaxValue; // Iterate over each of the // characters in the string s for ( int i = 0; i < n; i++) { // If the i-th character // is found to be '0' if (s[i] == '0' ) { right_0 -= 1; } else { left_1 += 1; } // Store the minimum of res // and right_0 + left_1 in res res = Math.Min(res, right_0 + left_1); } // Return the final result return res; } // Driver code public static void Main(String[] args) { string s = "001101" ; int count = minimumDeletions(s); Console.WriteLine(count); } } // This code is contributed by susmitakundugoaldanga. |
Javascript
<script> // JavaScript program for the above approach // Function to count minimum removals // required to arrange all 0s before 1s function minimumDeletions(s) { // Count the occurrences of 0 in s var right_0 = 0; var i; for (i=0;i<s.length;i++){ if (s[i]== '0' ) right_0++; } var left_1 = 0; // Size of the string var n = s.length; // Stores the minimum // number of removals required var res = 2147483647; // Iterate over each of the // characters in the string s for (i = 0; i < n; i++) { // If the i-th character // is found to be '0' if (s[i] == '0' ) { right_0 -= 1; } else { left_1 += 1; } // Store the minimum of res // and right_0 + left_1 in res res = Math.min(res, right_0 + left_1); } // Return the final result return res; } // Driver Code var s = "001101" ; var count = minimumDeletions(s); document.write(count); </script> |
1
Time Complexity: O(|S|)
Auxiliary Space: O(1)