nik1996's blog

By nik1996, history, 12 days ago, In English,

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 ?

 
 
 
 
  • Vote: I like it  
  • -2
  • Vote: I do not like it  

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by nik1996 (previous revision, new revision, compare).

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Length of a string ?

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

nxn dp

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you please elaborate how to solve using DP?

»
12 days ago, # |
Rev. 19   Vote: I like it -8 Vote: I do not like it

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:

  1. The sum of any sub-vector [1, k], where 1 ≤ k ≤ n, is positive.

  2. The total sum of the vector is zero.

#include <bits/stdc++.h>

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 as

g1(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

  1. the sum of any sub-vector [1, k] of q for all 1 ≤ k ≤ n is positive.

  2. the total sum of items in q is zero.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for the help. But how will you find count of all such balanced strings through this algo?

    • »
      »
      »
      12 days ago, # ^ |
      Rev. 19   Vote: I like it -8 Vote: I do not like it

      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.

»
12 days ago, # |
  Vote: I like it -8 Vote: I do not like it

just take every 2nd symbol to achieve a perfect balance

»
11 days ago, # |
Rev. 11   Vote: I like it -9 Vote: I do not like it

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; }
  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That's just a recursion. TLE for:()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      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.