Minimum Cost required to generate a balanced Bracket Sequence | Java program to implement the above approach ; Function to calculate the minimum cost required to generate a balanced bracket sequence ; Stores the count of unbalanced open brackets ; Stores the count of unbalanced closed brackets ; Stores the count of open brackets ; Stores the count of closed brackets ; If open brace is encountered ; Otherwise ; If no unbalanced open brackets are present ; Increase count of unbalanced closed brackets ; Otherwise ; Reduce count of unbalanced open brackets ; Increase count of closed brackets ; Calculate lower bound of minimum cost ; Reduce excess open or closed brackets to prevent counting them twice ; Update answer by adding minimum of removing both unbalanced open and closed brackets or inserting closed unbalanced brackets to end of String ; Print the result ; Driver Code
import java . util . * ; class GFG { static void minCost ( String str , int a , int b ) { int openUnbalanced = 0 ; int closedUnbalanced = 0 ; int openCount = 0 ; int closedCount = 0 ; for ( int i = 0 ; i < str . length ( ) ; i ++ ) { if ( str . charAt ( i ) == ' ( ' ) { openUnbalanced ++ ; openCount ++ ; } else { if ( openUnbalanced == 0 ) closedUnbalanced ++ ; else openUnbalanced -- ; closedCount ++ ; } } int result = a * ( Math . abs ( openCount - closedCount ) ) ; if ( closedCount > openCount ) closedUnbalanced -= ( closedCount - openCount ) ; if ( openCount > closedCount ) openUnbalanced -= ( openCount - closedCount ) ; result += Math . min ( a * ( openUnbalanced + closedUnbalanced ) , b * closedUnbalanced ) ; System . out . print ( result + "NEW_LINE"); } public static void main ( String [ ] args ) { String str = " ) ) ( ) ( ( ) ( ) ( " ; int A = 1 , B = 3 ; minCost ( str , A , B ) ; } }