Problem: brackets all over
Problem statement:
You are given a string containing only opening and closing brackets “(” and “)” of size m. You have to append 2 strings a and b in the order a+s+b and make them valid string of size n with the following properties,
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 answer with modulo 109 + 7.
Input Format
1st Line: n m 2nd Line: string s
Constraints
1<= m <= n <= 10^5
n-m <= 1200
Output Format
The number of combinations of a and b. Otherwise -1
Sample Input
4 2
((
Sample Output
1
Explanation
Only 1 possible case a="" , b="))"
Solution Link: https://ide.codingblocks.com/s/43500?_ga=2.135864953.954268262.1601992368-1083323979.1600702024
This solution link i got from discuss.codingblocks but i am not able to understand the solution.
Can you please explain me the solution. If possible please make a video explanation.
just explain me the segment of the code given below:
int pre = 0, bef = 0;
int L;
ll solve(int p, int open, int take){
if (p == L)return take && (open == 0);
ll &ret = dp[p][open][take];
if (ret != -1)return ret;
ret = 0;
if (!take){
if (open >= pre)
ret = (ret + solve(p + 1, open - pre +bef, 1)) % mod;
}
ret = (ret + solve(p + 1, open +1, take)) % mod;
if(open)ret = (ret + solve(p + 1, open - 1, take)) % mod;
return ret;
}