Brackets All Over

#1

Hello sir/ma’am,

I understood this question but i am not able to think of dp approach to solve this. Could you please help???

#2

Hello @Akshita99,

6 2
((
answer is 3. (())(), ((())) and ()(()).
This problem can be solved with dynamic programming as range of test cases is large the algorithm is given below:

  1. Calculate dp[i, j] : How many sequences of brackets of length i has balance j and intermediate balance never goes below zero (They form a prefix of a valid sequence of brackets).
  2. For the given sequence of length n calculate the resulting balance a and the minimum balance b.
  3. Try the length of the sequence added at the beginning c and its balance d. If - b ≤ d then add dp[c, d] × dp[m - n - c, d + a] to the answer.

Time complexity: O((n - m)^2)

Refer to this code : https://ide.codingblocks.com/s/250032

Hope, this would help.

#3

Hello sir, i am unable to understand this. Why are you making a 3d dp array in code? Also i am unable to understand your code. Could you please tell in detail or add comments to your code or share some video link where this dp approach is explained in detail.

#4

Hey @Akshita99,

Ignore that code.
I have mistakenly send you that.

The explanation for the problem using 2D DP:

Let dp[i][j] = number of bracket sequences of length i and balance j.
Let’s formulate a recurrence for dp[i][j]. To do that, consider a bracket sequence of length i and balance j.
There are two cases: It’s either the sequence ends with a ‘)’ or it ends with a ‘(’. Let’s consider these cases.

Case 1: Ends with ‘)’
Then if we remove that last bracket, the remaining sequence must have a balance of j + 1, because that last ‘)’ must have matched a ‘(’ and thus reduced the number of unmatched left brackets to j.
So we have dp[i][j] = dp[i — 1][j + 1] in this case.

Case 2: Ends with ‘(’
Then if we remove that last bracket, the remaining sequence must have a balance of j — 1, because that last ‘(’ matches nothing and only adds to the number of unmatched left brackets.
In this case, we have dp[i][j] = dp[i — 1][j — 1]

Since case 1 and case 2 are just partitions of dp[i][j], we combine them to get the total possibilities for dp[i][j]:
dp[i][j] = dp[i — 1][j + 1] + dp[i — 1][j — 1]

You can think of it as if you are given a sequence of brackets, first you should check the validity of these brackets eg: ())) - This is an incomplete sequence as number of opening and closing brackets are not same. And eg: ()() - This is a complete sequence. So now you have to make two different sequences which should balance the overall string a+s+b. So a can be independent or dependent on s or b and same applies to b. So you can make a dp to store the number by which the number of opening brackets are greater than the number of closing brackets till that index i. And then as stated in editorial you can add product of minimum balance dp and remaining balance dp to the answer.

Hope it Helps.

#5

So, if i understood it right then, dp will be of size [n] [n/2] because in any case balance cannot exceed n/2…right???

#6

Seems correct to me @Akshita99.

#7

Sir, could you please share your code link for reference??

#8

Sir, please reply…

#9

Sir please share reply…my course doubt support will end tomorrow, then this doubt will remain pending only…So please reply.

#10

Hey @Akshita99,

I am really sorry to reply this late.
I somehow missed your responses.

Now, coming to your doubt,
I don’t have the code with 2D DP, i have the one with 3D DP that i have already shared with you.

#11

Ok no problem sir. But can you please arrange the code or write it yourself using the 2d array approach you described and share it with me. I am unable to write the code using this logic. Also i tried to search online but couldn’t find any help. So it would be great if you could help with this one.

#12

Sure @Akshita99,

I’ll share the detail explanation of the code.
I didn’t found any video related to this.

#13

Hey @Akshita99,

Approach:

  1. It is quite obvious that we would only add opening brackets ‘(’ to string A and only closing brackets ‘)’ to string B

  2. Since the number of open and close brackets must be equal, we can never generate a valid string if n is odd.

  3. Count the total number of opening and closing brackets required to balanced the string. The opening brackets will go in string A and the closing brackets will go in string B.

  4. We start from pos = 0 and go till pos = n - m + 1. At each instance we consider three possibilities.

    4.1. if closingBrackets have not been implemented yet (close==0) and count of open brackets that we have implemented is more than required (open >= openBrackets) then, we implement the closing brackets required for string B and raise a flag for the same by marking close=1 also, change the open bracket count accordingly for this case
    4.2. if we have some open brackets then, put a closing bracket to balance it and decrease open count to denote there is one less unbalanced open bracket now
    4.3. add another opening bracket to the string so far. This bracket will be initially unbalanced.

  5. We add the results obtained from the three possibilities. We store and return this result.

  6. Continue the above process till pos < n-m+1.

  7. At pos == n-m+1, we must ensure that all required opening and closing brackets have been implemented. We do so by checking the status of out flag variable close i.e. check close==1. Also make sure there are no pending unbalanced open brackets (open==0).

Code:

#14

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.