Help me with the approach

#1

please provide me with detailed explanation of this question using dp approach.

#2

6 2
((
answer is 3. (())(), ((())) and ()(()).
This problem can be solved with dynamic programming as range of test cases is large the algorithm is given below:

  1. 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).

  2. For the given sequence of length n calculate the resulting balance a and the minimum balance b.

  3. 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)

#3

Can u please share the link to this problem if it is available on any website for more details of code and approach.

#4

Please reply fast,it has been more than a day

#5

Provide me with the code with necessary explanation

#6

This is the 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,

  1. At any index, number of opening brackets should be greater than closing brackets
  2. 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.

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="))"

#7

Refer to this code : https://ide.codingblocks.com/s/250032

#8

can u provide me any link to this question from any website

#9

https://hack.codingblocks.com/app/contests/1483/667/problem this is the link of question