Check if the bracket sequence can be balanced with at most one change in the position of a bracket | CPP implementation of the approach ; Function that returns true if the sequence can be balanced by changing the position of at most one bracket ; Odd length string can never be balanced ; Add ' ( ' in the beginning and ' ) ' in the end of the string ; If its an opening bracket then append it to the temp string ; If its a closing bracket ; There was an opening bracket to match it with ; No opening bracket to match it with ; Sequence is balanced ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool canBeBalanced ( string s , int n ) { if ( n % 2 == 1 ) return false ; string k = " ( " ; k += s + " ) " ; vector < string > d ; int cnt = 0 ; for ( int i = 0 ; i < k . length ( ) ; i ++ ) { if ( k [ i ] == ' ( ' ) d . push_back ( " ( " ) ; else { if ( d . size ( ) != 0 ) d . pop_back ( ) ; else return false ; } } if ( d . empty ( ) ) return true ; return false ; } int main ( int argc , char const * argv [ ] ) { string s = " ) ( ( ) " ; int n = s . length ( ) ; ( canBeBalanced ( s , n ) ) ? cout << " Yes " << endl : cout << " No " << endl ; return 0 ; }