### nik1996's blog

By nik1996, history, 2 months ago, ,

Given 2 strings of parenthesis. You need to make another string using these 2 strings such that in the resulting string, all the parenthesis are balanced. Ordering of parenthesis must not change, e.g. if u take 2 characters/parenthesis from 1st string, then order of these parenthesis must not change in resulting string. You need to tell number of balanced strings you can make. Examples: )) (( ans:2, you can make ()() and (())

Could anyone tell how this problem can be solved ?

•
• -2
•

 » 2 months ago, # |   0 Auto comment: topic has been updated by nik1996 (previous revision, new revision, compare).
 » 2 months ago, # |   0 Length of a string ?
•  » » 2 months ago, # ^ |   0 Length of each string <= 10^3.
 » 2 months ago, # |   0 nxn dp
•  » » 2 months ago, # ^ |   0 Could you please elaborate how to solve using DP?
 » 2 months ago, # | ← Rev. 19 →   -8 The following user-defined C++ data structure parentheses_string_t may be helpful. The constructor translates a parentheses-string argument s of length n to a base object vector< int >. As the ASCII code of the ( and ) characters are 40 and 41, the expression x = 81 - 2 * c translates c to 1 and -1, respectively. The necessary and sufficient conditions for s to be balanced are: The sum of any sub-vector [1, k], where 1 ≤ k ≤ n, is positive. The total sum of the vector is zero. #include using namespace std; struct parentheses_string_t: vector< int > { bool balanced; int sum; parentheses_string_t( const string &s ) : balanced( true ), sum( 0 ) { for( auto c: s ) { int x = 81 - 2 * c; push_back( x ), sum += x; if ( sum < 0 ) balanced = false; } if ( balanced and sum > 0 ) balanced = false; } }; int main() { ios_base::sync_with_stdio( false ), cin.tie( nullptr ), cout.tie( nullptr ); string s; cin >> s; parentheses_string_t p( s ); if ( p.balanced ) cout << "Yes"; else cout << "No"; } Let us assume that s1 and s2 are the input strings with lengths n1 and n2, respectively, and that p1 and p2 are constructed parentheses strings. Let the parentheses string q of length n = n1 + n2 be among the parentheses strings formed from p1 and p2. Let us define the selection function h(i), where 1 ≤ i ≤ n, such that h(i) = 1 implies that the parenthesis q(i) is selected from p1, and h(i) = 2 implies that q(i) is selected from p2. Let us define the selected sub-vectors [1, g1(i)] and [1, g2(i)] of p1 and p2, respectively, to form the sub-vector [1, i] in q, where g1(i) and g2(i) can be expressed asg1(i) = g1(i - 1) + 1 - (h(i) - 1) g2(i) = g2(i - 1) + (h(i) - 1) = i - g1(i)and g1(0) = g2(0) = 0. It follows that q(i) = ph(i)(gh(i)(i))The necessary and sufficient conditions for the balance of q are the sum of any sub-vector [1, k] of q for all 1 ≤ k ≤ n is positive. the total sum of items in q is zero.
•  » » 2 months ago, # ^ |   0 Thanks for the help. But how will you find count of all such balanced strings through this algo?
•  » » » 2 months ago, # ^ | ← Rev. 19 →   -8 The upper bound on the number of distinct balanced strings should be equal to the binomial coefficient n1-out-of-n as "h(1) - 1, ...., h(n) - 1" can be considered as an n-item bit-string that should contain n1 zeros and n2 ones whose exact positions vary over all possible balanced strings. Such bit-string can be considered as an input to an n-variable binary function whose value indicates whether or not the input bit-string corresponds to a balanced string. The previous comment hints about the balanced strings that satisfy the balance conditions, and about how a possible balanced string q may be generated from p1 and p2. Note that if g1(k - 1) = n1, then h(i) = 2 for all k ≤ i ≤ n. Similarly, if g2(k - 1) = n2, then h(i) = 1 for all k ≤ i ≤ n.
 » 2 months ago, # |   -8 just take every 2nd symbol to achieve a perfect balance
 » 2 months ago, # | ← Rev. 11 →   -9 The following is a simple program to count the number of distinct balanced strings based on the suggested data structure. It is assumed that the length of any balanced parentheses string constructed from s1 and s2 is n = n1 + n2, i.e. a possibly empty balanced parentheses string whose length is less than n is not counted. The program can be slightly updated to consider the latter requirement. int main() { ios_base::sync_with_stdio( false ), cin.tie( nullptr ), cout.tie( nullptr ); struct parentheses_strings_pair_t { int n1, n2, balanced, sum; parentheses_string_t *p1, *p2; void count_aux( int g1, int g2, int x ) { if ( x > 0 or sum > 0 ) sum += x, count( g1, g2 ), sum -= x; } void count( int g1, int g2 ) { if ( g1 == n1 and g2 == n2 ) balanced++; else { if ( g1 < n1 ) count_aux( g1 + 1, g2, p1->at( g1 ) ); if ( g2 < n2 ) count_aux( g1, g2 + 1, p2->at( g2 ) ); } } parentheses_strings_pair_t() : balanced( 0 ), sum( 0 ) { string s1, s2; cin >> s1 >> s2, n1 = s1.length(), n2 = s2.length(), p1 = new parentheses_string_t( s1 ), p2 = new parentheses_string_t( s2 ); if ( ( p1->sum + p2->sum ) == 0 ) count( 0, 0 ); } } x; cout << x.balanced; } 
•  » » 2 months ago, # ^ |   0 That's just a recursion. TLE for:()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()
•  » » » 2 months ago, # ^ |   -8 Sure, it is a simple recursive solution that works for small n. No claim was made in the previous post about its computational complexity for large n.