Unable to solve the problem Brackets All Over

#1

Hi!!

Can anyone explain how to solve this question (and if possible how do you go about such problems). I am unable to figure out a way to solve this.

Thanks in advance

#2

hello @Yash5646

every time we have to add open or close bracket or add the main string (just once)

let L = n-m+1 : n-m brackets to add + main string

DP state is (index , open , taken )

taken : to check if main string taken before or not

open : number of open brackets

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

bef : number of close brackets should be added after main string to make it valid

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

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

or add main string if ( open >= pre and taken == false ) then make open = open — pre + bef

check this for clarity->

think recursively

#3

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.