Brackets all over

#1

unable to understand the approach how to approach it?? explain me in step wise order in easy language

#2

the problem says that you are given a string s , it’s length m and a number n . You have generate all possible pairs of a and b such that:
a + s + b is a valid sequence of brackets of length exactly n .
For example if you are given s = “))” and n = 6(m = 2 obviously) then you can generate following pairs of a and b to make a+s+b a valid sequence:

“()((”       “))”       “”           // Remeber a and b can be blank also.
“((”       “))”       “()”
“(((”       “))”       “)”
“(()(”       “))”       “”
“((()”       “))”       “”

Hence, the ans for this testcase is 5. If there is no possible combination then print -1. Pls try the question now.

Hope this helps :slight_smile:

#3

Why m is equal to 2 obviously??

#4

m it is the size of input
)) these are 2 elements hence m= 2

#5

Mam can you tell me the approach for this what will be the dp state how to think… I am not able to do it correctly…

#6

This problem can be solved with dynamic programming:

  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)

#7

refer to this code in case u have some problem

#8

This problem is variation of some other problem?? If yess please send link mam… So that i can understand it properly

#9

have u done enough question of brackets
like there are a lot of question of longeest substring which is balanced( interms of closing opening brackets)
no of balanced sub-string in the string
generate paranthesis ( all possible)

this q needs a little more attention, can be done if u have done these basic questions

#10

No these questions are not there in challenges. I didn’t done them yet… Will I have to do them first to understand conceptually ??

#11

yes like having to think of how to approach by urself
u should have have these themselves
sharing links in chat

#12

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.