Unable to get the question

#1

Question is not clearly understood . can sm1 plz help to understand.

#2

@Yuganshu,

Let me explain the sample input step by step
input:
4 2
((
here n=4, m=2 and s=((

Now here s is the given string that we are talking about, m is the size of s (which is 2 in this case), we have to form a new string whose size is given to us- n(4 in this case)

Now, talking about the new string, we have to form it by appending a string a before it and by appending a string b after string s (This is what a+s+b means).
Now in our sample test case we are given n=4, m=2, s=((
we have to form a string of length 4, now that can only be (()), because we have to balance the brackets, we can NOT form a string like: ((() or ())(
therefore to form (()) we have one option a=""{i.e. a blank string} and b="))" {string with 2 closing brackets}.
Try solving this question using DP.
You can follow this approach of the time complexity O((n - m)^2)

  • 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.
#3

@sanchit.bansal06 what is DP here

#4

@Yuganshu,
DP is dynamic programming. If you have not covered that yet, you can do it through recursion as well.

#5

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.