Longest valid Parentheses

Given a string consisting of opening and closing parenthesis, find length of the longest valid parenthesis substring.

Example
Input : ((()
Output : 2

Input: )()())
Output : 4

Input: ()(()))))
Output: 6

Solution:

• We will stack to maintain index of all opening brackets “(“.
• When we encounter “(” we’ll push index of this in stack
• When we encounter “)” then there could be there possible cases
  • Case 1. Stack is already empty
    • means all valid parenthesis already consumed and after this new start
  • Case 2. After pop element from stack, it becomes empty
  • Case 3. And even after poping from stack is not empty.

Algorithm:

• Create empty stack
• Set maxLen = 0, last = -1
• Iterate parenthesis from start to end
  • If currentCharacter is "(" then
    • stack.push(i)
  • Else
    • If stack is empty then,
      • last = i
    • Else
      • stack.pop
      • If stack is empty then,
        • maxLen = Math.max(maxLen, i - last)
      • Else
        • maxLen = Math.max(maxLen, i - stack.peek())
• Return maxLen

Latest Source Code:
Github: LongestValidParentheses.java

Output:

Longest Valid Parentheses of ((() :2
Longest Valid Parentheses of )()())()()()() :8
Longest Valid Parentheses of ()(())))) :6
Longest Valid Parentheses of )()()) :4
Longest Valid Parentheses of ()()() :6
Longest Valid Parentheses of  :0
Longest Valid Parentheses of (((( :0
Longest Valid Parentheses of (((() :2
Longest Valid Parentheses of (((())( :4
Longest Valid Parentheses of ()(() :2
Longest Valid Parentheses of ()(()) :6