Brackets All Over-Doubt

#1

I have tried it using simple greedy implementation but i am unable to solve this problem,please help

#2

Hey Saksham, greedy approach will not work for this problem try to think it using dynamic programming.

#3

okay will try it using DP but can you please give me some approach as to how to start?

#4

Yes Sure. You can follow this approach of the time complexity O((n - m)^2)

  • Calculate dp[i, j] : How many sequences of brackets of length i has balance j and intermediate balance never goes below zero (They form a prefix of a valid sequence of brackets).

  • For the given sequence of length n calculate the resulting balance a and the minimum balance b.

  • Try the length of the sequence added at the beginning c and its balance d. If - b ≤ d then add dp[c, d] Ă— dp[m - n - c, d + a] to the answer.

#5

Hey Saksham, as you are not responding to this thread, I am marking your doubt as Resolved for now. Re-open it if required. And please mark your doubts as resolved in your course’s “Ask Doubt” section, when your doubt is resolved.

#6

Can somebody explain what this line means by balance?
How many sequences of brackets of length i has balance j and intermediate balance never goes below zero
(They form a prefix of a valid sequence of brackets).