My code is producing correct output for smaller test cases but not working for bigger testcases .
Brackets All Over
still waiting for your response…
This problem can be solved with dynamic programming to reduce the time complexity because of time complexity your code is not working for bigger ones.The algorithm is as :
-
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.
Time complexity: O((n - m)^2)
I do have used DP and I’m not getting TLE. My output is Wrong. Please do have a look on my code.
Well,thanks for the code, but i would like to know the problem in my code and, if you want i could send you a detailed explanation of my Code.
If, it’s not possible for you, so, please give the detailed explanation of the referred code, as, the editorial explanation isn’t enough for me to understand the code.
Well, thanks for the code, but i would like to know the problem in my code and, if you want i could send you a detailed explanation of my Code.
If, it’s not possible for you, so, please give the detailed explanation of the referred code, as, the editorial explanation isn’t enough for me to understand the code.
@singh.balpreet965 hi , you are given a string which contains only ‘(’ and ‘)’. Size of the string will be m. You have to append two strings one in prefix and another one in suffix to make that string valid and conditions for validity are given below:
- At any index, number of opening brackets should be greater than closing brackets
- No. of opening and closing brackets should be equal. You have to tell number of combinations of string a and b if its possible, otherwise print “0” Print the asnwer with modulo 10^9 + 7.
Check this code,and dry run it its similiar to your code and logic:
https://ide.codingblocks.com/s/43500?_ga=2.3807669.445908857.1592901853-1868378134.1563105121
Feel free to ask any doubt.
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.