I am not getting how to solve it

#1

can you give me some hint?

#2

Hey @Vipin_coder
This question is a clear dynamic programming question and can be solved by dp only because it is a clear combinatorial optimization problem.
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.

#3

IF it is DP problem , why it is given in string problem, no can solve on string bases only.

#4

@Vipin_coder
can solve on string bases only.
Answer Nope

#6

if no, then why dp problem is given in string section, this course is not well structured?

#7

can you explain recursive code ???

#8

@Vipin_coder,
https://ide.codingblocks.com/s/351546 I have attached the recursive code for reference. This will give you TLE for 4/5 test cases though (since the test cases are large).

Here we are checking every possible combination possible for the input string and returning the final answer

#9

i am not able to understand the logic to solve this problem, help me.

#10

@Vipin_coder

Approach

  1. It is quite obvious that we would only add opening brackets ‘(’ to string A and only closing brackets ‘)’ to string B
  2. Since the number of open and close brackets must be equal, we can never generate a valid string if n is odd.
  3. Count the total number of opening and closing brackets required to balanced the string. The opening brackets will go in string A and the closing brackets will go in string B.
  4. We start from pos = 0 and go till pos = n - m + 1. At each instance we consider three possibilities.
  • if closingBrackets have not been implemented yet (close==0) and count of open brackets that we have implemented is more than required (open >= openBrackets) then, we implement the closing brackets required for string B and raise a flag for the same by marking close=1 also, change the open bracket count accordingly for this case
  • if we have some open brackets then, put a closing bracket to balance it and decrease open count to denote there is one less unbalanced open bracket now
  • add another opening bracket to the string so far. This bracket will be initially unbalanced.
  1. We add the results obtained from the three possibilities. We store and return this result.
  2. Continue the above process till pos < n-m+1.
  3. At pos == n-m+1, we must ensure that all required opening and closing brackets have been implemented. We do so by checking the status of out flag variable close i.e. check close==1. Also make sure there are no pending unbalanced open brackets (open==0).

You can refer to this code.

Brackets all over
#11

opening bracket only in string a and closing only in b.
a+s+b if s="()", n=6, m=2;
then a="()", b="()" , a+s+b="()()()";
it is also possible , so how A only contain opening bracket???

#12

@Vipin_coder
No. See there are multiple ways to construct a and b and you could possibly put closing brackets in a and opening brackets in b. But then the relation would go out of your hand and the answer would simply be infinity. Since I can put as many opening and closing brackets pair in a or b as I want and there’s no stoppping to it.
You must define a base case for every recurrence relation and the condition to put opening brackets in a and closing in b is one of those. This is to avoid infinite recursion.