Brackets all Over

#1

what should be output for following test case
4 1
(

#2

hi

I think 4

  1. a= ( b= ))
  2. a="" b= ())
  3. a="" b=)()
  4. a=() b=)

I might miss some case :stuck_out_tongue:
do let me know if you find any.

#3

any help of top down dp approach to solve this problem will we appreciate.
if you have any idea.
let me know.

#4

Hi

GO to this approach if you have tried enough from your side.
do take one one hint at a time.

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).

For the given sequence of length n calculate the resulting balance a and the minimum balance b.

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)

Hit like if you get it!
Cheers!

#5

still not getting below line.
If - b ≤ d then add dp[c, d] × dp[m - n - c, d + a]

#6

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.