Minimum removals to make a string concatenation of a substring of 0 s followed by a substring of 1 s | Java program for the above approach ; Function to count minimum removals required to make a given string concatenation of substring of 0 s followed by substring of 1 s ; Stores the length of the string ; Precompute the count of 0 s ; Check for the last character ; Traverse and update zeroCount array ; If current character is 0 , ; Update aCount [ i ] as aCount [ i + 1 ] + 1 ; Update as aCount [ i + 1 ] ; Keeps track of deleted 1 s ; Stores the count of removals ; Traverse the array ; If current character is 1 ; Update ans ; If all 1 s are deleted ; Return the minimum number of deletions ; Driver Code
import java . io . * ; class GFG { public static int minimumDeletions ( String s ) { int n = s . length ( ) ; int zeroCount [ ] = new int [ n ] ; zeroCount [ n - 1 ] = ( s . charAt ( n - 1 ) == '0' ) ? 1 : 0 ; for ( int i = n - 2 ; i >= 0 ; i -- ) zeroCount [ i ] = ( s . charAt ( i ) == '0' ) ? zeroCount [ i + 1 ] + 1 : zeroCount [ i + 1 ] ; int oneCount = 0 ; int ans = Integer . MAX_VALUE ; for ( int i = 0 ; i < n ; i ++ ) { if ( s . charAt ( i ) == '1' ) { ans = Math . min ( ans , oneCount + zeroCount [ i ] ) ; oneCount ++ ; } } ans = Math . min ( ans , oneCount ) ; return ( ans == Integer . MAX_VALUE ) ? 0 : ans ; } public static void main ( String [ ] args ) { String str = "00101101" ; System . out . println ( minimumDeletions ( str ) ) ; } }