Check if it is possible to obtain a Balanced Parenthesis by shifting brackets to either end at most K times | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void minimumMoves ( string s , int n , int k ) { if ( n & 1 ) { cout << " No " ; return ; } int countOpen = count ( s . begin ( ) , s . end ( ) , ' ( ' ) ; int countClose = count ( s . begin ( ) , s . end ( ) , ' ) ' ) ; if ( countOpen != countClose ) { cout << " No " ; return ; } int ans = 0 ; int cnt = 0 ; for ( int i = 0 ; i < n ; ++ i ) { if ( s [ i ] == ' ( ' ) ++ cnt ; else { -- cnt ; if ( cnt < 0 ) { cnt = 0 ; ++ ans ; } } } if ( ans <= k ) cout << " Yes " ; else cout << " No " ; } int main ( ) { string S = " ) ( " ; int K = 1 ; minimumMoves ( S , S . length ( ) , K ) ; return 0 ; }