Problem is not clear to me

#1

i cant understand what the problem is trying to say

#2

@jatin111,

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.