+1 vote

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring. For "(()", the longest valid parentheses substring is "()", which has length = 2.

Anyone point me on how to solve this?

asked Jul 21, 2018 in Computer Science - IT by anonymous | 17 views

1 Answer

+1 vote

It is quite easy, actually. The Algorithm to do this is listed below -

1) Create an empty stack and push -1 to it. The first element of stack is used to provide base for next valid string. 

2) Initialize result as 0.

3) If the character is '(' i.e. str[i] == '('), push index 'i' to the stack. 

4) Else

   a) Pop an item from stack 

   b) If stack is not empty, then find length of current valid sub string by taking difference between current index and top of the stack. If current length is more than result, then update the result.

   c) If stack is empty, push current index as base for next valid sub string.

5) Return result.

answered Feb 25 by Likhit_N