@shameek.agarwal
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.
Hope it Helps.
