Leetcode - Longest Valid Parentheses (Python)

April 2021 Leetcode Challenge
Leetcode - Leetcode - Longest Valid Parentheses #32
Difficulty: Hard

[@def__init]

props for showing the right to left example case to make it very clear for 2nd solution :)

[@sudheerdadala3417]

Clean and Clear! Why does the Clicking sound excites me more ,Lol.

[@Apurvsankhyadhar]

Genius!

[@isaiahr7041]

Is this considered twompointwrs due 5o the usage of he l and r variables?

[@valshin]

-1 is a mystery

[@shashank_r94]

Two reasons:
1. Stack can't be empty - In case all parenthesis are valid you need the first (leftmost) index to find the length Cases - "()" or "()()()(("
2. using (-1) instead of 0 (let's say) then ( i - stack[-1]) will give an incorrect result while subtracting with 0 for "()" will give you 1-0 = 1 which instead should be 2(1- (-1)).
Hope it helps !!

[@VladBurlutsky]

Great!

[@aniketwattamwar1514]

thanks for this !

[@timc3406]

My pleasure

[@tdog6127]

So helpful!

[@timc3406]

Glad you think so!

[@JustMusics]

Anyone knows why it must be -1? I tried other number seems cannot

[@vaibhavsharma9103]

what if we have ')' in the starting in this case you will try to pop() and stack is empty so it will give error so we push -1 before we start traversing

[@janmichaelaustria620]

This problem made me cry..... :( And on Day 3 too

[@timc3406]

Hang in there!

[@iam_a_sad_khan]

I feel so stupid after seeing these solutions. I was able to solve this problem using dp, and my solution ran in 0ms, but my solution is so complicated compared to these solutions.

[@alejandroruiz8766]

Can you explain the -1 reason?

[@aa10259]

consider this case to understand--> "(())"

[@shuyinlam8541]

just consider ')', if the stack is empty, stack.pop() will throw error

[@zeta563]

Thanks for the helpful video. But I have question that what if s starts with several ")"? Then popping empty stack leads to error..

[@BogdanHladiuc]

That's why there is -1 pushed to the stack at the beginning.