Help needed in approach

#1

sir i am not able to think of how to proceed this problem like i can figure out that at every index i need to store how many invalid ‘(’ and ‘)’ i have encountered so far but i am not able to extend this idea into dp solution

#2

plz provide me with some hint

#3

You have problem in which question @Shobhit_kumar?

#4

Please share link of that problem statement .or you can copy and paste it here also.

#5

@Shobhit_kumar, I’ll describe this approach below (with a few minor tweaks).

The recurrence used is f(i, j) which returns the number of valid bracket sequences from position 1 to i with j more opening brackets than closing brackets. For convenience let’s call the difference between opening and closing brackets simply the difference. If we are at position i and we need j more “[” than “]”, then we can obtain that by two ways.

We put a “[” at position i to get a difference j. This means that there must have been a difference of j-1 upto position i-1.
We put a “]” at position i to get a difference j. This implies that there must have been a difference of j+1 upto position i−1.
We are also given a set of positions s which must contain “[”. For such positions, option 2 is unavailable. For j<0 naturally f(i, j)=0 because we are proceeding from left to right and if we have more “]” than “[” we can never end up with a valid sequence. Again f(0,0)=1 as the empty sequence with difference 0 is valid. Also f(0,j) for j>0 is 0

Putting all of this together,

f(i,j)= 
0  if j<0 or i=0,j>0
1 if i=0,j=0
f(i−1,j−1)  if i is in s
f(i−1,j−1)+f(i−1,j+1) otherwise

​

The final answer will be f(2n,0) as 2n is the last position in our sequence and we want the sequence to be valid, so we need difference 0.

you can refer to the solution itself it has nice explanation

In case of any doubt feel free to ask
mark your doubt as resolved if u got the answer.

#6

sir in the explanation part u said that assume there are more [ than ] and in the first case you are putting [ shouldn’t it be ] bcoz already [ is in excess…plz clarify this

#7

what is lt and gt in the explanation??

#8

Yes there are more [ than ] , I am describing this case only in first test case.

#9

Yes there are more [ than ] , I am describing this case in which we have more [ then ]
This means that when we put a “[” at position i it gives us a difference j. It means that there must have been a difference of j-1 upto position i-1.
And when We put a “]” at position i It gives us a difference j. This implies that there must have been a difference of j+1 upto position i−1.

#10

sir how does this idea came to your mind?? i mean this idea doesn’t seam to be very intuitive enough…

#11

Dp questions are like this only bro , when you will go in interview you will face limited questions on advanced DSA topics , unless and until you are giving interview in companies which have competitions like codeagon. Try different types of dp questions on different platform as this topic is not easy to get but after continuous work on it you can surely get it.

#12

and sir how in this i will fill my dp table ?? can you help me with some pseudo code of this…

#13

Yes, see this that states can be
dp[bracket_idx][opening_brackets_remaining][closing_brackets_remaining]
now recurrence is intuitive.
if current index has to be [ then
dp[i][j][k] = solve(i+1,j-1,k) only if j>0 else there is no way so return 0;
else this idx can be [ or ]
dp[i][j][k] = solve(i+1,j-1,k) // if j>0
dp[i][j][k] += solve(i+1.j,k-1) // if k>0 and j<k so that option is balanced/valid.

#14

dp[i][j][k] += solve(i+1.j,k-1) // if k>0 and j<k so that option is balanced/valid. how do you say this that if option will be balanced only when ] remaining is greater than ] remaining??

#15

okay okay as we are traversing from left to right so at any point of time we should have more ] remaining then [ otherwise it won’t be possible to form valid string

#16

Yes @Shobhit_kumar you got it right.

#17

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.