Minimum Swaps for Bracket Balancing | Java Program to count swaps required to balance string ; stores total number of Left and Right brackets encountered ; swap stores the number of swaps required imbalance maintains the number of imbalance pair ; increment count of Left bracket ; swaps count is last swap count + total number imbalanced brackets ; imbalance decremented by 1 as it solved only one imbalance of Left and Right ; increment count of Right bracket ; imbalance is reset to current difference between Left and Right brackets ; Driver code
public class BalanceParan { static long swapCount ( String s ) { char [ ] chars = s . toCharArray ( ) ; int countLeft = 0 , countRight = 0 ; int swap = 0 , imbalance = 0 ; for ( int i = 0 ; i < chars . length ; i ++ ) { if ( chars [ i ] == ' [ ' ) { countLeft ++ ; if ( imbalance > 0 ) { swap += imbalance ; imbalance -- ; } } else if ( chars [ i ] == ' ] ' ) { countRight ++ ; imbalance = ( countRight - countLeft ) ; } } return swap ; } public static void main ( String args [ ] ) { String s = " [ ] ] [ ] [ " ; System . out . println ( swapCount ( s ) ) ; s = " [ [ ] [ ] ] " ; System . out . println ( swapCount ( s ) ) ; } }