three testcases showing wrong answer.
pls tell the correct code.
Brackets all over
what i get from your code is you are first balancing the given string and then making combinations for the remaining characters (correct me if i am wrong in getting your code login), which is not the case here, the characters you have included in balancing the given string will also be part of combinations.
Try to apply Dynamic Programming in it, using the given 2 conditions in the problem statement.
can u tell in the form of a code.
please try to solve on your own, its not beneficial if i give you the code, I can help you with logic.
Lets say 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.
1 Like