Longest Valid Parentheses

Longest Valid ParenthesesMar 1 '12

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.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

Analysis

lastValidIndx keeps track of the index of the starting point of the longest valid parantheses. An empty stack will increment the lastValidIndx. So consider this string )))))( in this case, the lastValidIndx will be 5. Any valid parantheses will be counted from the lastValidIndx as currentIndx-lastValidIndx+1.

maxLength: keeps track of the length of the maximum length of valid parantheses seen so far. 

Unclosed parantheses: Consider the string ()(()(), in this case the length of the maximum parantheses is 4 and not 6. Whenever a ) is seen we pop the current top of the stack. If the, stack is not empty then there is an unbclosed parantheses in the stack. We then count the parantheses as starting from the index of this unclosed parantheses instead of counting it from lastValidIndx as we do for the case of stack empty case (no unclosed parantheses)

Time Complexity:   O(n)