Check if it is possible to obtain a Balanced Parenthesis by shifting brackets to either end at most K times | Java program for the above approach ; Function to check if a valid parenthesis can be obtained by moving characters to either end at most K number of times ; Base Case 1 ; Count of ' ( ' and ' ) ' ; Base Case 2 ; Store the count of moves required to make a valid parenthesis ; Traverse the string ; Increment cnt if opening bracket has occurred ; Otherwise , decrement cnt by 1 ; Decrement cnt by 1 ; If cnt is negative ; Update the cnt ; Increment the ans ; If ans is at most K , then print Yes . Otherwise print No ; Driver Code
import java . io . * ; import java . lang . * ; import java . util . * ; class GFG { static void minimumMoves ( String s , int n , int k ) { if ( n % 2 == 1 ) { System . out . println ( " No " ) ; return ; } int countOpen = 0 , countClose = 0 ; for ( char ch : s . toCharArray ( ) ) if ( ch == ' ( ' ) countOpen ++ ; else if ( ch == ' ) ' ) countClose ++ ; if ( countOpen != countClose ) { System . out . println ( " No " ) ; return ; } int ans = 0 ; int cnt = 0 ; for ( int i = 0 ; i < n ; ++ i ) { if ( s . charAt ( i ) == ' ( ' ) ++ cnt ; else { -- cnt ; if ( cnt < 0 ) { cnt = 0 ; ++ ans ; } } } if ( ans <= k ) System . out . println ( " Yes " ) ; else System . out . println ( " No " ) ; } public static void main ( String [ ] args ) { String S = " ) ( " ; int K = 1 ; minimumMoves ( S , S . length ( ) , K ) ; } }