only 1 test case is passing and in the solution, it is given use DP. Can you please help me solve this question without using DP and what Logic will be used
I am not able to get correct solution for this
@apoorvsingh27,
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}.
You can use recursion or any other method as well, but it will give you a TLE. DP is the best method for this. I have explained the DP approach. Let me know if you have any doubts.
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.
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.