Given binary string str of length N, the task is to find the minimum number of characters required to be deleted from the given binary string to make a substring of 0s followed by a substring of 1s.
Examples:
Input: str = “00101101”
Output: 2
Explanation: Removing str[2] and str[6] or removing str[3] and str[6] modifies the given binary string to “000111” or “001111” respectively. The number of removals required in both the cases is 2, which is the minimum possible.Input: str = “111000001111”
Output: 3
Brute Force Approach:
- Initialize the minimum number of deletions required to be the length of the input string since we can delete all characters in the worst case to satisfy the condition.
- Iterate over each character i in the input string.
- Calculate the number of 1s before i and the number of 0s after i using the count() function in the STL.
- Calculate the total number of deletions required to make a substring of 0s followed by a substring of 1s using i as the midpoint.
- Update the minimum number of deletions required if the current substring requires fewer deletions.
- Return the minimum number of deletions required.
Below is the code of above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count minimum removals // required to make a given string // concatenation of substring of 0s // followed by substring of 1s int minimumDeletions(string s) { int n = s.length(); int minDeletions = n; for ( int i=0;i<n;i++) { int numOnesBefore = count(s.begin(), s.begin()+i, '1' ); int numZerosAfter = count(s.begin()+i, s.end(), '0' ); minDeletions = min(minDeletions, numOnesBefore + numZerosAfter); } return minDeletions; } // Driver Code int main() { string stri = "00101101" ; cout << minimumDeletions(stri) << endl; return 0; } |
Java
import java.util.*; public class Main { // Function to count minimum removals // required to make a given string // concatenation of substring of 0s // followed by substring of 1s public static int minimumDeletions(String s) { int n = s.length(); int minDeletions = n; for ( int i= 0 ;i<n;i++) { int numOnesBefore = count(s.substring( 0 , i), '1' ); int numZerosAfter = count(s.substring(i), '0' ); minDeletions = Math.min(minDeletions, numOnesBefore + numZerosAfter); } return minDeletions; } // Utility function to count occurrences of a character in a string public static int count(String s, char c) { int count = 0 ; for ( int i = 0 ; i < s.length(); i++) { if (s.charAt(i) == c) { count++; } } return count; } // Driver Code public static void main(String[] args) { String stri = "00101101" ; System.out.println(minimumDeletions(stri)); } } |
Python
# Function to count minimum removals # required to make a given string # concatenation of substring of 0s # followed by substring of 1s def minimum_deletions(s): n = len (s) min_deletions = n for i in range (n): num_ones_before = s[:i].count( '1' ) num_zeros_after = s[i:].count( '0' ) min_deletions = min (min_deletions, num_ones_before + num_zeros_after) return min_deletions # Driver Code if __name__ = = "__main__" : stri = "00101101" print (minimum_deletions(stri)) |
C#
using System; class Program { // Function to count minimum removals // required to make a given string // concatenation of substring of 0s // followed by substring of 1s static int MinimumDeletions( string s) { int n = s.Length; int minDeletions = n; for ( int i = 0; i < n; i++) { int numOnesBefore = CountOccurrences(s.Substring(0, i), '1' ); int numZerosAfter = CountOccurrences(s.Substring(i), '0' ); minDeletions = Math.Min(minDeletions, numOnesBefore + numZerosAfter); } return minDeletions; } // Helper function to count occurrences of a character in a string static int CountOccurrences( string input, char target) { int count = 0; foreach ( char c in input) { if (c == target) count++; } return count; } // Driver Code static void Main() { string stri = "00101101" ; Console.WriteLine(MinimumDeletions(stri)); } } |
Javascript
// Function to count minimum removals // required to make a given string // concatenation of substring of 0s // followed by substring of 1s function minimumDeletions(s) { const n = s.length; let minDeletions = n; for (let i = 0; i < n; i++) { const numOnesBefore = s.substring(0, i).split( '1' ).length - 1; const numZerosAfter = s.substring(i).split( '0' ).length - 1; minDeletions = Math.min(minDeletions, numOnesBefore + numZerosAfter); } return minDeletions; } // Driver Code const stri = "00101101" ; console.log(minimumDeletions(stri)); |
2
Time Complexity: O(N^2), where N is the length of the input string. The outer loop iterates over all possible positions in the string, and the count function inside the loop has a time complexity of O(N) for each call, giving an overall time complexity of O(N^2).
Auxiliary Space: O(1) because we are not using any additional data structures to store information about the input string.
Efficient Approach: The above approach can be optimized by having an auxiliary space that keeps the count of the number of 0s after 1s. Using this pre-computation, the time complexity can be improved by a factor of N. Below are the steps:
- Initialize a variable, say ans, to store the minimum number of characters required to be deleted.
- Initialize an array, say zeroCount[], to count the number of 0s present after a given index.
- Traverse the string str from the end over the range [N – 2, 0] and if the current character is 0, then update zeroCount[i] as (zeroCount[i + 1] + 1). Otherwise, update zeroCount[i] as zeroCount[i + 1].
- Initialize a variable, say oneCount, to count the number of 1s.
- Traverse the given string again. For every character found to be ‘1’, update ans as the minimum of ans and (oneCount + zeroCount[i]).
- After the above steps, if the value of ans remains same as its initialized value, then 0 characters are required to be deleted. Otherwise, ans is the required number of characters to be deleted.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> #include <iostream> using namespace std; // Function to count minimum removals // required to make a given string // concatenation of substring of 0s // followed by substring of 1s int minimumDeletions(string s) { // Stores the length of the string int n = s.size(); // Precompute the count of 0s int zeroCount[n]; // Check for the last character zeroCount[n - 1] = (s[n - 1] == '0' ) ? 1 : 0; // Traverse and update zeroCount array for ( int i = n - 2; i >= 0; i--) // If current character is 0, zeroCount[i] = (s[i] == '0' ) ? // Update aCount[i] as // aCount[i + 1] + 1 zeroCount[i + 1] + 1 : // Update as aCount[i + 1] zeroCount[i + 1]; // Keeps track of deleted 1s int oneCount = 0; // Stores the count of removals int ans = INT_MAX; // Traverse the array for ( int i = 0; i < n; i++) { // If current character is 1 if (s[i] == '1' ) { // Update ans ans = min(ans, oneCount + zeroCount[i]); oneCount++; } } // If all 1s are deleted ans = min(ans, oneCount); // Return the minimum // number of deletions return (ans == INT_MAX) ? 0 : ans; } // Driver Code int main() { string stri = "00101101" ; cout << minimumDeletions(stri) << endl; return 0; } // This code is contributed by AnkThon |
Java
// Java program for the above approach import java.io.*; class GFG { // Function to count minimum removals // required to make a given string // concatenation of substring of 0s // followed by substring of 1s public static int minimumDeletions(String s) { // Stores the length of the string int n = s.length(); // Precompute the count of 0s int zeroCount[] = new int [n]; // Check for the last character zeroCount[n - 1 ] = (s.charAt(n - 1 ) == '0' ) ? 1 : 0 ; // Traverse and update zeroCount array for ( int i = n - 2 ; i >= 0 ; i--) // If current character is 0, zeroCount[i] = (s.charAt(i) == '0' ) // Update aCount[i] as // aCount[i + 1] + 1 ? zeroCount[i + 1 ] + 1 // Update as aCount[i + 1] : zeroCount[i + 1 ]; // Keeps track of deleted 1s int oneCount = 0 ; // Stores the count of removals int ans = Integer.MAX_VALUE; // Traverse the array for ( int i = 0 ; i < n; i++) { // If current character is 1 if (s.charAt(i) == '1' ) { // Update ans ans = Math.min(ans, oneCount + zeroCount[i]); oneCount++; } } // If all 1s are deleted ans = Math.min(ans, oneCount); // Return the minimum // number of deletions return (ans == Integer.MAX_VALUE) ? 0 : ans; } // Driver Code public static void main(String[] args) { String str = "00101101" ; System.out.println( minimumDeletions(str)); } } |
Python3
# Python3 program for the above approach # Function to count minimum removals # required to make a given string # concatenation of substring of 0s # followed by substring of 1s def minimumDeletions(s): # Stores the length of the string n = len (s) # Precompute the count of 0s zeroCount = [ 0 for i in range (n)] # Check for the last character zeroCount[n - 1 ] = 1 if s[n - 1 ] = = '0' else 0 # Traverse and update zeroCount array for i in range (n - 2 , - 1 , - 1 ): # If current character is 0, zeroCount[i] = zeroCount[i + 1 ] + 1 if (s[i] = = '0' ) else zeroCount[i + 1 ] # Keeps track of deleted 1s oneCount = 0 # Stores the count of removals ans = 10 * * 9 # Traverse the array for i in range (n): # If current character is 1 if (s[i] = = '1' ): # Update ans ans = min (ans,oneCount + zeroCount[i]) oneCount + = 1 # If all 1s are deleted ans = min (ans, oneCount) # Return the minimum # number of deletions return 0 if ans = = 10 * * 18 else ans # Driver Code if __name__ = = '__main__' : str = "00101101" print (minimumDeletions( str )) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { // Function to count minimum removals // required to make a given string // concatenation of substring of 0s // followed by substring of 1s public static int minimumDeletions(String s) { // Stores the length of the string int n = s.Length; // Precompute the count of 0s int []zeroCount = new int [n]; // Check for the last character zeroCount[n - 1] = (s[n - 1] == '0' ) ? 1 : 0; // Traverse and update zeroCount array for ( int i = n - 2; i >= 0; i--) // If current character is 0, zeroCount[i] = (s[i] == '0' ) // Update aCount[i] as // aCount[i + 1] + 1 ? zeroCount[i + 1] + 1 // Update as aCount[i + 1] : zeroCount[i + 1]; // Keeps track of deleted 1s int oneCount = 0; // Stores the count of removals int ans = int .MaxValue; // Traverse the array for ( int i = 0; i < n; i++) { // If current character is 1 if (s[i] == '1' ) { // Update ans ans = Math.Min(ans, oneCount + zeroCount[i]); oneCount++; } } // If all 1s are deleted ans = Math.Min(ans, oneCount); // Return the minimum // number of deletions return (ans == int .MaxValue) ? 0 : ans; } // Driver Code public static void Main(String[] args) { String str = "00101101" ; Console.WriteLine( minimumDeletions(str)); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript program for above approach // Function to count minimum removals // required to make a given string // concatenation of substring of 0s // followed by substring of 1s function minimumDeletions(s) { // Stores the length of the string let n = s.length; // Precompute the count of 0s let zeroCount = []; // Check for the last character zeroCount[n - 1] = (s[n - 1] == '0' ) ? 1 : 0; // Traverse and update zeroCount array for (let i = n - 2; i >= 0; i--) // If current character is 0, zeroCount[i] = (s[i] == '0' ) // Update aCount[i] as // aCount[i + 1] + 1 ? zeroCount[i + 1] + 1 // Update as aCount[i + 1] : zeroCount[i + 1]; // Keeps track of deleted 1s let oneCount = 0; // Stores the count of removals let ans = Number.MAX_VALUE; // Traverse the array for (let i = 0; i < n; i++) { // If current character is 1 if (s[i] == '1' ) { // Update ans ans = Math.min(ans, oneCount + zeroCount[i]); oneCount++; } } // If all 1s are deleted ans = Math.min(ans, oneCount); // Return the minimum // number of deletions return (ans == Number.MAX_VALUE) ? 0 : ans; } // Driver Code let str = "00101101" ; document.write( minimumDeletions(str)); </script> |
2
Time Complexity: O(N)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!