Facing Difficulty in Brackets All Over Problem

#1

I am facing difficulty in finding the approach to this problem.Please help.

#2

@ap8730390 Hi bro,
This question is a clear dynamic programming question and can be solved by dp only because it is a clear combinatorial optimization problem.

Just what you have to do is think of a recursive approach first.

I am explaining the question to you.

Actually the question says that you have to generate the string of size n given m is the length of given string
Where m<=n

Now you have to generate a bracket string which is balanced
By adding a prefix and suffix string to given string s
Now the prefix string should have opening brackets greater than closing brackets, because the string should be overall be balanced.

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.

You can also refer to my code here, its a good question so I recommend you to try:-


If your doubt is clear then resolve it!

#3

Why is 3D Dp used in this code?

#4

I am Still facing difficulty in understanding your 3D dp solution, please explain me the solution :frowning:

#5

@ap8730390 bro if you know dp, the cache dimensions in dp is decided by states of recurrence, you can clearly see that there are three variable states in function signature.

DP state here is DP state is (index , openBrac , flag ).

openBrac : number of open brackets
flag: If the original string is taken or not.

lets calculate two values ,
prefix: number of open brackets should be added before main string to make it valid

postfix : number of close brackets should be added after main string to make it valid
Because the string should be balanced.

every time we try to add open bracket and increase (openBrac)

or add close bracket if number of open brackets >= 1 and decrease (openBrac)

or add main string if ( openBrac >= prefix and flag == false ) then make openBrac = openBrac - prefix + postfix

Bro this question is very good, if your dp is not strong then i recommend first you solve all classical problems then switch to this problem, also dry run the code for the above example.