i am not able to solve this question.please guide meβ¦and please suggest me solution that neither include dynamic programing nor oops concept.
Not able to approach this question
@Coder9124 Hi, A question which requires dynamic programming paradigm can only be solved through dp obviously. 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.
Now try it first, if have any doubt lemme know.