Im not able to understand the problem

#1

its very difficult to analyze that what exactly question is asking . Can you please help me out with this

#2

hey @1999atrijsharma
It is a dynamic programming
if you know dynamic programming then i will explain otherwise leave it for now

#3

please help me with some other test cases so that i can understand what exactly the question is .

#4

i know DP now so please explain the question to me .

#5

Can you please help me out with this

#6

Actually the question says that you have to generate the string of size n given m is the length of given string
Where m<=n

Now you have to generate a bracket string which is balanced
By adding a prefix and suffix string to given string s
Now the prefix string should have opening brackets greater than closing brackets, because the string should be overall be balanced.

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.

#7

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.
  • 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
  • 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
  • add another opening bracket to the string so far. This bracket will be initially unbalanced.
  1. We add the results obtained from the three possibilities. We store and return this result.
  2. Continue the above process till pos < n-m+1.
  3. 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).

You can refer to this code

#8

im unable to code it , can you help me with the sample code .

#9

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.

#10

Maam i tried , but i was not able to code . Can you please help me with the code .

#11

refer to this: