Check if it is possible to obtain a Balanced Parenthesis by shifting brackets to either end at most K times | 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
def minimumMoves ( s , n , k ) : NEW_LINE INDENT if ( n & 1 ) : NEW_LINE INDENT print ( " No " ) NEW_LINE return NEW_LINE DEDENT DEDENT ' NEW_LINE INDENT countOpen = s . count ( ' ( ' ) NEW_LINE countClose = s . count ( ' ) ' ) NEW_LINE if ( countOpen != countClose ) : NEW_LINE INDENT print ( " No " ) NEW_LINE return NEW_LINE DEDENT ans = 0 NEW_LINE cnt = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( s [ i ] == ' ( ' ) : NEW_LINE INDENT cnt += 1 NEW_LINE DEDENT else : NEW_LINE INDENT cnt -= 1 NEW_LINE if ( cnt < 0 ) : NEW_LINE INDENT cnt = 0 NEW_LINE ans += 1 NEW_LINE DEDENT DEDENT DEDENT if ( ans <= k ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : S = " ) ( " NEW_LINE INDENT K = 1 NEW_LINE minimumMoves ( S , len ( S ) , K ) NEW_LINE DEDENT