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.
the problem says that you are given a string s , it’s length m and a number n . You have generate all possible pairs of a and b such that:
a + s + b is a valid sequence of brackets of length exactly n .
For example if you are given s = “))” and n = 6(m = 2 obviously) then you can generate following pairs of a and b to make a+s+b a valid sequence:
“()((” “))” “” // Remeber a and b can be blank also.
“((” “))” “()”
“(((” “))” “)”
“(()(” “))” “”
“((()” “))” “”
Hence, the ans for this testcase is 5. If there is no possible combination then print -1. Pls try the question now